The security steps you list are pretty good. I would highly recommend a managed VPS if you don't know what you're doing and the sites are mission critical. If you're just using the VPS to play around and learn linux, that's fine.
One more option which you may not have thought of, would be to get an outside management company to set up and "harden" the VPS for you initially. Most will do it within an hour or two, and shouldn't charge you much more than a one-time $20 or $30 fee. Then you know everything is set up correctly.
You can also opt for a control panel. There are some free ones out there (webmin and kloxo come to mind) and paid ones like DirectAdmin and cPanel. All will make managing the server and setting up your websites a lot easier.
As far as the oversold VPS, if you're paying shared hosting prices for your VPS, chances are it's oversold. Dedicated resources are expensive. Just as an easy example, let's say the provider has a VPS server with 16GB of RAM, and pays about $300/mo. Just the provider's cost is $18.75/GB of RAM. You could expect to pay anywhere from $21-22 or so and up for a 1GB VPS server...about $10 for a 512mb server, and $5 for a 256mb server. Just an example.
OpenVZ is almost guaranteed to be oversold, as is Virtuozzo. Without getting too complicated, Xen RAM can be overcommitted (though it causes all sorts of issues, and isn't quite the same as overselling), and disk space cannot be oversold. The only thing that can truly be oversold is CPU and bandwidth. Chances are that if you go with a Xen VPS, you will be getting completely dedicated resources. Of course, you're going to pay for those resources. You aren't going to find a Xen VPS with 1GB of RAM for $5 or $10, unless it's a special and the provider is using it as a loss-leader to rope you in.