I have really appreciated Appigo's Todo.app combined with Toodledo's web service, despite some sync issues .
Now, however, there's a serious alternative. Toodledo has launched their own iPhone and iPod Touch client.
The Toodledo app should have a big advantage. The data model should be an exact match for the web site. Same fields, same allowed values (same data dictionary), etc. No funny mappings for priorities, no missing context fields, etc. One vendor to own the synchronization problem.
On the other hand, Appigo has an integrated Notebook app. Their app is mature and reliable, and I've worked around the data model issues. Their aesthetics are much better than Toodledo, and they're not tied to a single web service. If, heaven forfend, Google should ever add tasks to their calendar app, we know Appigo would be on it like flies on ... well .. .quickly anyway.
I think a newcomer could go either way. They're both pay apps, so price might sway some people. (Toodledo is cheaper.)
I'll stay with Todo.app for now -- it works and I like their Notebook.
Competition is good though.
 I think these are on Toodledo's side; I've found that transactions don't always complete as expected when I use their web GUI).