That's like asking the difference between a Lamborghini and a Porche 911 Turbo.
Do you have any experience with any of them? If not, get your hands on an Android phone, open the app drawer, and say hello to iOS. That's a drastic oversimplification, and I admit to it freely, but that's essentially what iOS is. Android gives you the ability to customize your user experience to far greater degrees than iOS, but iOS is far, far simpler, and in actuality much more stable. On the other hand, it locks you into iTunes so completely that it's insane.
However, I'm sure someone with more iOS experience than I have will be able to help you out more. Your best bet is to play with Android, and a Fascinate in particular, to get some idea of what you're looking at. As far as I'm concerned, though, if the phone's free I'd go with that and run with it rather than locking yourself into a 2-year contract since you might hate the phone.
Even if you hate the Fascinate you'll at least be secure in the knowledge you can change it any time you want and can afford to.