You can reboot via VNC as you normally would when sitting at the computer.
The key is to make sure VNC is configured to start automatically when the machine starts up; that way it will come back online when the reboot is finished - from the remote end just reboot, wait a while, then reconnect (if it responds to pings then you can run a continuous ping if you're impatient to see when it comes back, a few seconds after that [allowing for the VNC server to start] you will be good to connect again).
Also, what sort of download/upload rate for the remote computer is really necessary for solid remote experience?
It doesn't matter really, VNC will rarely get you a solid remote experience. If you have an internet connection try e.g. TeamViewer. I use TeamViewer for remote site access frequently (also you don't have to deal with knowing the IP address or allowing incoming connections through firewalls, great for sites with lots of IT red tape or a complex internal network). While it seems odd that it would perform better it just has a much better compression and transfer algorithm.
As an example, I am currently working on a project that consists of two machines (both running Ubuntu, and both very high performance) connected directly via copper, gigabit. One at the work site and one in a nearby control room. VNC is still sluggish and choppy. The site machine has a second interface with an internet connection, and is running TeamViewer in addition to VNC.
If I connect to the machine via TeamViewer from my laptop (via public wifi, out to the internet, back to the site and through all the building's internal networking) it is two full orders of magnitude faster and clearer than a VNC connection over direct gigabit ethernet. Even connecting to it with my smart phone is significantly smoother.
If you don't have internet access then you're stuck with VNC. You could try other VNC servers / clients instead of Ubuntu's built-in one; although it is unlikely you will achieve the performance of e.g. TeamViewer or, say, RDP on Windows (not sure if OSX has an RDP-like remote interface). Lower the quality settings too, it can help (e.g. heavy jpeg compression, or switch to 8-bit color; turn off the desktop background, use a "plain" looking window theme on the remote machine with lots of solid colors, etc.).