How do I install and run Tomcat on port 80 as my only web server? (Rooted Ubuntu box)

Run tomcat as the tomcat user. I don't think you should ever run tomcat as root. It exposes the potential for a larger security risk than running it as an unprivileged user.

Tomcat's HTTP serving is a bit lacking for some stuff, so i'd always suggest that you have a http server as a frontend. If you don't want apache, there's always Nginx. This is especially true if you wanted HTTP Basic or Digest auth.

I'd suggest that you start off with tomcat's default memory settings, then tune them as and when you need to. With no knowledge of the app's memory profile, it's difficult to give you any hard and fast figures.

If you're using Ubuntu on your vps, you can just apt-get install tomcat6 and it should work out of the "box". Even on Centos5.4, the tomcat5 package from yum works with minimal config changes.

I seriously advise that you use a lightweight server in front of your tomcat instance though. This gives you better granular control over security than Tomcat's "Security Manager"

I have Tomcat6 running on a Virtual Machine which runs my hudson CI server, I think i've given it about 256MB of RAM, and it's perfectly happy.

Even if you do not have enough space to run a full-fledge web-server in front of Tomcat, you can consider running a reverse-proxy like pound. At the very least, it can quickly stop random connections to your server if configured correctly. Just point pound to the internal port 8080 that Tomcat listens on.