User Customization and Themes

I have a question about choosing the right theme.

Here is what we are trying to do.

We are building a network for professionals and small businesses that will allow them to sign up and get started with a new site on our network.
- We are planning on using one StudioPress theme that they get as a default to start with.
- Our plan was to have a members area that would allow them to get access to hundreds of videos on how to manipulate their site to suit their own business, including widgets, colors, logo, and anything else that can be changed.

Our problem is that we just ran into the fact that all of the new users will be running off of one theme file, so whatever is done to the theme file for one site would effect every other site on the network. Am I correct in this?

So, our idea of allowing them to change things via the APPEARANCE-EDITOR section doesn't really work I guess? That is automatically turned hidden for everyone other than super-admins?

If this is true, what would you say would be the best way to remedy this issue. Use a theme with different css options that would allow them to choose colors etc? A theme that has a built in logo change area in the admin?

I really like the studiopress themes as I have used them for years and know them well, so any ideas on how to keep using studiopress instead of changing to a new set of themes would be greatly appreciated.

Thanks for any input.