We want to start mobile development (starting with Android). Our two most likely candidate tools at this time are Phonegap and Xamarin. I'd like to hear about any thoughts on and experiences with either of these packages. Am trying to decide what to use for a first prototype (business software).

Any thoughts on Android Studio or IntelliJ are welcome too, although I'm not too found on programming Java.

Don't really know too much about it. But I can say I would choose PhoneGap if I know HTML and CSS and Javascript very well. If I were a C# developer familiar with .NET I would go for Xamarin.
Well, for what it's worth, my penny of advise...

pritaeas any specific reason why you want to use 3rd party library that is mix of HTML5 and Ajax instead of native Android code base?

Both frameworks will be always slower then native code, they are more likely introduce various bugs, and they always behind current Android development.

As for the IDEs I do use Android Studio on daily bases and does work great as long you are using Gradle as your build automation tool. However you have to remember this is not official release therefore some stuff is missing like multi module testing, project test coverage

IntelliJ is more round-up IDE given that has longer history (Android Studio is base on IntelliJ so it inheritted lot of good stuff). However advantage of IntelliJ is support of Ant, Maven and Gradle build tools, support for multi module testing and coverage with Cobertura, Emma and Jacoco.

Nevertheless I'm not sure if either of these IDEs support Phonegap or Xamarin.

Sorry if I gave negative opinion on above frameworks, but I'm native Android dev and not really friend of these "cross platform" frameworks

Not sure yet if Android will be our (only) target platform. Just started with this, and no Java programmers in-house, although I personally don't see the problem.

Phonegap and Titanium Appcelerator are great for small, simple applications, but you quickly run into performance issues, especially on lower-end devices.

Xamarin is a great tool, and certainly something to consider if you only have C# skills in-house, but, it's still not as easy as native Android applications. My biggest gripe with Xamarin is getting layouts to work as expected.

Compared to how simple and easy it is to create layouts in Eclipse or Android Studio, I'd have to say take the week or two required to migrate from C# to Java.

great for small, simple applications

Good enough.

not as easy as native Android applications

I have no intention on writing native apps.

take the week or two required to migrate from C# to Java

Easy enough for me, but not an option.