I know that virtualization creates partitions which are isolated from each another. How many different partitions can one server hold? Or would that be based on memory?
I think its dependent on the specs of your server. The processes and what the requirements are placed on the machine. More powerful server and lower demands on the server mean more machines can be run.
That is correct, here is the link to bodhost's dedicated servers: Dedicated Servers | Dedicated Server Hosting
You can always look at that link then ask the question again depending on which one is going to match your requirements.
I am interested in figuring out how many virtual machines can be run on the different specs too. When you get some combination in mind (don't forget the demand you are going to place on the server), toss them out there.