I've been using Panic's Prompt. It does color, SSH keys (including PEMs, if you've got a need to work with EC2), runs Vim and Emacs just fine, and most definitely works beautifully on a non-jailbroken phone. The soft keyboard also provides convenient access to escape, tab, and other keys that you need frequently when you're working with a terminal. Properly configured, Prompt also provides superb auto-complete that actually makes using a terminal on an iPhone palatable. Alternatively, Prompt works great with a Bluetooth keyboard--a combination that has proved excellent when I'm on the road and something goes wrong with a server.
Plus, Prompt is a universal app, so if you've got an iPad, you can use the bigger screen when you've got it, and still rely on the iPhone's size when you don't.
My only complaint is that Prompt can be a bit slow. I'm not sure how much of that is Prompt's fault, and how much of that is my cell phone's network not being quite up-to-snuff. But the slowness hasn't honestly