One of my favorite first games I write for mobile devices is Hangman. It's a simple two player game that works well on handhelds.
Player 1 enters a secret word and passes the device to player 2. Usually at this point I'll actually display "This is Hangman, press [whatever] to play". Even people who have never seen your phone before will get-it instantly.
Then display the blanks "_ _ _ _ _ _" and provide some intuitive way for them to select letters. As they guess wrong, start drawing the hangman, spell out the word "HANGMAN" or just keep score.
Eventually they will get it right or lose. In either case prompt player 2 to enter a new secret word. Then display the results of the last game "Last score: XX Press [whatever] to play again". Now player 2 can pass the device back to player 1 who starts the next game.
I like this game because the logic is simple, it's two player but not really interactive like tic-tac-toe, and you can play it without talking. I used to pass my HP calculator back and forth during class in school without ever having to verbally explain how to play the game.
I've often thought of writing this in J2ME and using text messaging to pass secret words to remote players. You'd have to be able to capture the incoming SMS messages but I can kind of do this on Sprint PCS phones.