It's not quite a native iPhone game, but it's one of the best games I've seen for the iPhone yet-- Roger sent us his version of Battleship (which is actually a pen and paper game that predates Milton Bradley's version-- I did not know that), called Battlefleet.
It's super easy to play, and turns out to be not only a faithful recreation, but includes a lot of little fun graphical touches as well-- the ships look good, and bombs drop and explode or splash into the water. There's also three difficulty options, and you can even track wins and losses over multiple games. Unfortunately, there's no way to play two player (as it would probably require some networking wizardry), but it's as good a game as you could ask of a solo version. And the computer opponent is just plain devious, anyway-- I hate it when he finds my aircraft carrier and then just goes to town.
You sank my battleship!