There are many factors to consider such as where the biggest market is, and so on. But ignoring those factors and thinking just about technical and money issues, the clear answer is start with Android.
The Android SDK is totally free. The iPhone dev tools need a Mac, so if you're not a Mac user, you need to buy a Mac. If you're not a Mac user, then it's probably a safe bet that you don't already know Objective C, which you'll need for iPhone. You don't even need a phone, there is an emulator that works wonderfully. It's very rare that I've made something that works in the emulator but doesn't work or works differently on a real phone. So the emulator is quite excellent.
Android programming is Java, and is very similar to C#.
Android development is much more approachable and easy for development (for getting started at least) than Objective C and iPhone.
There are many online resources available, but the book "Hello, Android" is actually very good. It's dated, though, goes back to version 1.5 of the SDK and we're at 2.2 today, but the fundamentals for getting started are pretty much the same.
You may decide to go another way, but in a handful of hours you can be writing your first Hello World program on Android free of charge. Even if you decide to start on another platform, you can hardly go wrong by giving Android a shot first.
Another thing that's worth noting is that Android is way easier to sell and distribute your apps than iPhone, making it a better place to start. There is no app approval process with the Android marketplace, so you can have your app posted for sure without wondering whether the powers that be will approve your first app for sale or to give away.
It bears mentioning that if you go the Microsoft route, your C# experience will transfer almost completely, and you'll be amazed at how close the compact SDK is to writing plain Windows apps. (At least, it was in 2007, the last time I wrote a Microsoft phone app.) But forget I brought this up-- if you want to be a serious phone developer for consumers, I recommend you forget about Microsoft at least for now.