I use
Remember The Milk. The app itself is free, but to use the service beyond the 15-day trial account, you need to sign up for their "pro" subscription which is $25/year. Some people complain about this, but I find the service invaluable. The app on the iPhone is great, the best to do app I've tried, but the main webapp is even better, and syncing between the two has always been seamless for me, unline some other services.
I've also tried
Things from Cultured Code along with their Mac application. The Mac app is superb, but the iPhone app is quite buggy, and they've taken a long time to fix bugs historically, and in the end I grew tired of waiting.
I was a beta tester for
Pocket Informant, and would recommend it for syncing with the online todo service
Toodledo. It also syncs calendar events through Google Calendar, so if you want an all-in-one app for calendars and todos, then this would be my recommendation. The devs (WebIS) are very responsive to feedback and are very communicative regarding bug fixes, feature enhancements and future updates. All other devs should take a lesson from these guys. However I ended up going back to Remember The Milk myself, as it suits my needs more than Toodledo, and I love the simplicity of their service.
I've also tried
Todo from Appigo, and this is another very polished app that syncs well with Toodledo, Remember the Milk and iCal.
If you need a really high-end solution for calendars, contacts, todos, projects, objectives etc., then
Daylite Touch is an absolutely stunning app, but with a $50/year licensing, on top of the high cost of their desktop (Mac) solution, it doesn't come cheap.
Other ones I've tried are:
iMExchange, good if you want to sync tasks & notes with an exchange server.
CalTodo, a basic iCal todo syncing app.
Toodledo's own native app.
OmniFocus is very good if you have a Mac and their desktop app, but a bit too bloated for my needs.
SmartTime is rubbish....IMO.