I'm a biology and chemistry double major, but in my previous life (the first time I went to college) I majored in everything from music education to english to hotel/motel management to theater/dance. As a result I'm currently a senior by credits but not going to graduate with a degree until 2006.
My advice would be to major in whatever you like the most out of those choices. Getting an education paid for is always nice. Just make sure you do extremely well in your prereqs....
I will warn you that out of the majors your employer would pay for it will be tough to find a job in the "field" in history, psychology, spanish, and humanities, unless you get education certified. You would probably need to get a graduate degree in any of those if things didn't work out med school wise. Out of your choices tho, those are the ones I'd find the most intriguing and interesting to study tho. In fact I'm thinking of minoring in psychology myself 🙂
Like I said tho, just do whatever you feel the most attracted to, and make sure you do well in it. The diversity will only serve you well when you end up applying to med school...
Good luck!
--Jessica, UCCS