Don't get me wrong, I love American capitalism, and I don't think innovation trumps all other factors (like reliability). The myth of Microsoft innovation is just one of those peculiar cultural myths that, in this case, blocks out the reality for people who don't work in the field.
The facade of innovation works for larger items too. Why create a vehicle that lasts long after the 5 year bodywork warranty when you're just reducing your market. Entice people with the new model, make sure your goods don't last too long - that appears to be the capitalist way.
Gmail
AdSense/AdWords
Google Scholar
Google Maps / Google Earth
Google Books
Google Image Search
Google Apps
Google Code
Google News
Chrome
SketchUp
"Innovation" in the strong sense of something super-radically new is not that important, at least to me. Let's not get distracted by that.
The reason I like Google is that things they make are well done. They don't have jingly-bobs popping up all over the place and lots of new "features" that actually make things worse. Their stuff has generally started simple and good, and gotten better. I don't find myself resenting using Google's stuff, cursing at the stupid bugs all the time. Their products have lots of nice little touches, like the way Google search will evaluate a mathematical expression or look up the time in a given location, and it searches PDF and PPT files and renders them decently in HTML. Google Groups now searches bulletin boards and discussion lists as well as Usenet groups. Google Maps does a really nice job of finding bus routes in San Francisco. It often just does what you want it to, without your having to ask, and without getting in the way.
When using most Microsoft products, I usually have the feeling that some "manager" has decided that there's no money in making things work nicely, but there is money in "shipping it". For example, the auto-numbering bugs that have been in MS-Word more than 10 years now and annoy people every single day.
When we bought Keyhole, we were able to bring a serious amount of datacenter and network resources to the problem of serving tiles, make the consumer client free for use and offer web interfaces to the same. I think that was non-trivial and quite innovative.
That Michael Jones and the Keyholers were able to take advantage of that expertise speaks to their remarkable ability as well. (I really like when I get the chance to work with MTJ, he's brilliant)
So while the team at keyhole were themselves hugely innovative, the combined work of google + keyhole was amazing, more so than either group could have done on their own.
To say that a Google or a microsoft can only be innovative if you only count those people who are hired specifically and only though one mechanism and at one time if seems unrealistic . It doesn't recognize that a company is the combined knowledge of the past work in the space, the employees experience gained at university and previous employers, and through knowledge and employees gained via acquisitions.
(this is not to say that all acquisitions work out, either)
Say what you will about their software - but there is no argument that they know how to run a business.
Any recommendations for what I should have done instead?
You don't need to respond to every qualm or counterpoint if others do it for you.
If Microsoft is so bad, why is everybody buying it? The "shady business practices" theory is just too easy. And even if that was the only reason: I guess then they innovated in the sector of "shady business practices". They certainly did not become so big through sheer luck.
These guys have something else: a strong bargaining position. "Innovation is a fleeting advantage." Cornering a market, setting up barriers to entry—those are time-tested and effective ways to make serious money.