Incoming links always a good thing. As already mentioned though, the value of them are going to vary based upon value of the site linking to you. Meaning also as mentioned, new sites are going to have no value as they are probably not even indexed yet themselves.
I really can't speak with authority about linking on the same server, but if you do a whois search the registrant of record / site owner does not change because of what server the site is hosted at. However, it has been my experience that this can do wonders, again if the linking site has good value.
No effect opening links in new windows.
One point I might bring up is this. I would really think over the business plan here. Offering free hosting to numbers of sites means also opening the doors to a lot of customer service issues. Be ready for frequent contacts on "whats my password", "my outlook doesn't work", "I can't get my ftp to connect", "your server is down", and if the hosting permits dynamic activity aka data driven content, you're in for a lot of fun with customer service as well.
I myself wouldn't even consider giving away hosting to the number of accounts that would be required to make a difference for the simple fee of a backlink. You will find the price in time servicing these accounts put you in an entire other business.
Hope That Helps
GF -