I love multiplayer on iPhone, so my vote goes to Cestos and Galactic Empires. They are pretty much opposites.
Cestos is a two player marbles game. Perfect if your data connection is a little bit sketchy or slow, it's turn based with actions executed simultaneously. Games last up to a max of probably 3 minutes, but with one touch u can re-play the same opponent if they're willing. If there was a few dozen more people in the game lounge it would be perfect. And it's FREE!
Galactic empires is a very simple, text only persistent universe, with thousands of players. Very slow moving, expect to get attacked a lot when u start out, but with persistence u can set up enuf defenses to keep the wolves at bay, and then wage some war of your own. Also FREE!
Enjoy!