Services in IBM's parlance are quite often high dollar customizations to IBM products or high dollar custom applications built on top of them or integrating them.
I'm not sure 'services' or a similar concept exists for MS. I hope they do pull in a genius outsider like Lou Gerstner though, I really hope he's/she's willing to make some very tough choices and honestly, I kind of hope that some of MS's better products are spun out in to their own independent companies to fly on their own. Fundamentally, whatever happens, MS is going to change in some ways and while I don't trust them or like them, I really hope it's a positive change that benefits the whole industry.
They've gotten much bigger on corporate services: They compete with Accenture on large software implementations, and do big EDS style outsourcing projects. In doing this they've shifted away from hardware preferences.
They've also bought many enterprise software packages which lend themselves to implementations and ongoing support.
From a shareholders perspective Gerstner was very aggressive about share repurchases, or giving money back. One problem with big companies is they get so much money that they start wasting it. A company can appear very large and strong, but do nothing for the shareholders, if they're just pissing away retained earnings. (One could argue that Microsoft was guilty of this)
Also, investor-wise people were happy with what he did. A thriving company doing i-have-no-idea-what is a better investment than a sinking mainframe company.