Well with an online game you are going to want reliability and performance as your top goals. So the most horsepower and bandwidth the better for supporting multiple people. You should look into a host that can provide you with a linux/unix system with as much RAM and CPU power you can get for a reasonable price range. They should also have sufficient bandwidth capacity for the number of users you are looking at.
For 100 users you are not going to need top of the line, but you will want to make sure the host is linux with a few gigs of RAM, lots of disk space, has a good connection to the Internet, probably has some mysql databases.
You can get good hosts anywhere from 5-10 USD a month.
And lastly if you want instant fame and god like popularity, just be sure to link to DIC somewhere on it. hahaha jk