It is not illegal to host a web proxy. You can sign up with anyone from the many VPS companies and setup your own proxy.
However, keep in mind that if your IPs are used to attack other networks, abuse complaints will reach your hoster and they will shut you down if you dont deal with it. There are some hosters that look away but they will also be eventually shut down if they sponser enough malicious activity.
Regarding your question about the number of users, it really depends on the bandwidth package you have, the machine you use and the type of connections the proxy is handling.
If I were you, I would setup one of the low end VPS machines and install an out of the box open source proxy (like Squid or Gizmo). Make sure you deny access from any unknown users - best thing if you know your user's IP allow only them using IP tables. Otherwise, some username/password authentication can do.
Hope this helps.