[jrockway]

If the "normal person" is incidentally using Ubuntu and Cyanogenmod, all we have to do is plug the phone in via USB, turn on tethering on the phone, click "HTC Android Phone" on "the two computers on the screen" (nm-applet), and that's that.

This hasn't been my experience. Mine is similar, except you don't even have to click anything: the usb network device is detected, and network-manager immediately attempts to get an IP address. Then you're online.

There is no way it could possibly be easier.