Marco.org

From iphone-reviews:

★★★★★ (iTMS)

If you like strategy games, this is probably the best you can get on an iPhone. Intuitive interface; short battles; and a good difficulty ramp, perfect both for learning the game and to give you one hell of a challenge when climbing up the ranks. I read on Hassey’s blog that multiplayer will be coming in the next version as well, which will make this game truly ultimate :)

This game is excellent. Highly recommended.