I haven't worked much with Appcelerator Titanium, but I'll put my understanding of it at the end.
I can speak a bit more to the differences between PhoneGap and Xamarin, as I work with these two 5 (or more) days a week.
If you are already familiar with C# and JavaScript, then the question I guess is, does the business logic lie in an area more suited to JavaScript or C#?
PhoneGap is designed to allow you to write your applications using JavaScript and HTML, and much of the functionality that they do provide is designed to mimic the current proposed specifications for the functionality that will eventually be available with HTML5. The big benefit of PhoneGap in my opinion is that since you are doing the UI with HTML, it can easily be ported between platforms. The downside is, because you are porting the same UI between platforms, it won't feel quite as at home in any of them. Meaning that, without further tweaking, you can't have an application that feels fully at home in iOS and Android, meaning that it has the iOS and Android styling. The majority of your logic can be written using JavaScript, which means it too can be ported between platforms. If the current PhoneGap API does most of what you want, then it's pretty easy to get up and running. If however, there are things you need from the device that are not in the API, then you get into the fun of Plugin Development, which will be in the native device's development language of choice (with one caveat, but I'll get to that), which means you would likely need to get up to speed quickly in Objective-C, Java, etc. The good thing about this model, is you can usually adapt many different native libraries to serve your purpose, and many libraries already have PhoneGap Plugins. Although you might not have much experience with these languages, there will at least be a plethora of examples to work from.
Xamarin.iOS and Xamarin.Android (also known as MonoTouch and MonoDroid), are designed to allow you to have one library of business logic, and use this within your application, and hook it into your UI. Because it's based on .NET 4.5, you get some awesome lambda notations, LINQ, and a whole bunch of other C# awesomeness, which can make writing your business logic less painful. The downside here is that Xamarin expects that you want to make your applications truly feel native on the device, which means that you will likely end up rewriting your UI for each platform, before hooking it together with the business logic. I have heard about MvvmCross, which is designed to make this easier for you, but I haven't really had an opportunity to look into it yet. If you are familiar with the MVVM system in C#, you may want to have a look at this. When it comes to native libraries, MonoTouch becomes interesting. MonoTouch requires a Binding library to tell your C# code how to link into the underlying Objective-C and Java code. Some of these libraries will already have bindings, but if yours doesn't, creating one can be, interesting. Xamarin has made a tool called Objective Sharpie to help with this process, and for the most part, it will get you 95% of the way there. The remaining 5% will probably take 80% of your time attempting to bind a library.
Update
As noted in the comments below, Xamarin has released Xamarin Forms which is a cross platform abstraction around the platform specific UI components. Definitely worth the look.
Now because I said I would get to it, the caveat mentioned in PhoneGap above, is a Hybrid approach, where you can use PhoneGap for part, and Xamarin for part. I have quite a bit of experience with this, and I would caution you against it. Highly. The problem with this, is it is such a no mans' land that if you ever run into issues, almost no one will have come close to what you're doing, and will question what you're trying to do greatly. It is doable, but it's definitely not fun.
As I mentioned before, I haven't worked much with Appcelerator Titanium, So for the differences between them, I will suggest you look at Comparing Titanium and Phonegap or Comparison between Corona, Phonegap, Titanium as it has a very thorough description of the differences. Basically, it appears that though they both use JavaScript, how that JavaScript is interpreted is slightly different. With Titanium, you will be writing your JavaScript to the Titanium SDK, whereas with PhoneGap, you will write your application using the PhoneGap API. As PhoneGap is very HTML5 and JavaScript standards compliant, you can use pretty much any JavaScript libraries you want, such as JQuery. With PhoneGap your user interface will be composed of HTML and CSS. With Titanium, you will benefit from their Cross-platform XML which appears to generate Native components. This means it will definitely have a better native look and feel.