Hi Brad,
Im not an "expert" but do a fair bit if developing in my spare time. My understanding is that this shouldn't affect you from an SEO stand point. Its only the databases and administration files behind the scenes that are ran from the same place, and if set up correctly google bots dont crawl these anyway. Each site is still technically self contained and a website in its own right. You are not trying to anything naughty like linking between the sites to boost rankings etc and are treating them as separate entities. Also I believe the "store" system in magento is designed with exactly what you are doing in mind.
In terms of servers, lots of websites bar the absolutely huge ones out there are hosted on shared servers anyway, you just simply don't see it and the bots know its not an important factor (unless in extreme cases where dodgy stuff is happening i believe). The personal sites I develop are technically sub domains and I still get them ranking completely independently and treated as separate entities.
Please dont take just my opinion as the answer, wait for someone with a little more experience, I dont want to just spam the obvious but it might also be worth a post on the Magento help forums as the community there may be able to offer some magento SEO expertise that this forum cant.