My website is hosted by a third party and I don't have console access to the machine so I used their management console application to install DotNetNuke on my site. 

I successfully added some modules and created a simple skin - all is great so far.  Now, I'd like to change the look-n-feel of the SolPartMenu but can not figure out how to do it.  I've read through as many posts here as I can find on the subject but either I'm lost in the terminology (newbie where the post assumed knowledge...) or you need to have access to the file structure on the physical machine.

Does anyone know how to change the SolPartMenu using only the DotNetNuke application interface?  Thanks!

Typically you would update the css file in the simple skin you created to change the look of the menu.  While this is not part of the application interface, it is part of how you created a skin.  If you need an interface inside of DNN you could install my free menu module.  As a module it provides complete control over the look and feel of your menu by assigning the styles of the menu inside the module's settings.  It can be "bound" to the DotNetNuke tab collection.

If I had a choice between the two I probably would change the css from my skin over my module, for assigning a module to be visible on all pages is kind of a klunky way to get site navigation.

Hope this helps,