Well, if you have the money, you simply can NOT go wrong with Things. It's available for the Mac, the iPhone and the iPad, but you have to buy all three apps. It's probably the best, easiest, and most beautiful GTD app out there. Second would be Omnifocus. Omnifocus is much more complex for those of you who are Project Managers building aircraft carriers at the shipyard in Newport News.
If you want something just to use on the iPhone, I would suggest StickyDoo. I really like that one.