As a counter point, I've also used Phonegap extensively.
Titanium is going to give you a native app. They provide extensive api's so you can write in javascript and reliably cross-compile to multiple platforms. There's downsides to this though, and that's where it was a tradeoff for me.
For me, Titanium didn't offer enough control for what was being offered. Once I was invested using their platform for developing a mobile app, I would have been locked in. If there was something I needed to do on my app that wasn't supported by their API, I was basically SOL (shit out of luck).
Phonegap, on the other hand, is largely html/css/js running in a WebView with an ObjC wrapper that provides access to hardware functionality. If you write your app entirely within the framework, you're limited by the performance of UIWebView. This can seriously be an issue for certain kinds of apps.
On the other hand, Phonegap worked great as a way for me to build the UI using the web technologies I know best. Since its just a framework, I have full access to all of the project files and source code, so I can add or change stuff if I need to. An app I released back in April needed to play video. There was no capability for this native to Phonegap, so I had to add the code myself. ObjC was new to me, but I was able to work through it.
Phonegap is setup to let you build to other platforms too, but you have to set up the dev environments for Android, etc, separately.
Ultimately what it comes down to is what you need, and what you are looking to do. For me, Phonegap was the better route. For others, it might be Appcelerator.
None of us could believe a venture backed company would put out such crap s/w. Anywho, we went ahead and developed the app in Obj-C (our issue was we didn't have a Mac and needed to build something for the iPhone).