Here's what we ended up doing.
Enable iCloud's "Back to My Mac" feature and enable remote management options under Sharing in system preferences, following these instructions:
The tricky part is that Grandpa's Mac isn't just sitting on the internet with its own IP address, it sits behind his wireless router (as is the case for most of us). So you have to go into the router's admin settings and forward ports 5500, 5800, and 5900 to Grandpa's IP on the local network (192.168.something). The above link had hints about that but we also googled for his specific router, plus "port forwarding". Apparently port 5900 is the standard for VNC and something somewhere told us ports 5500 and 5800 were needed as well, which seemed to be true.
Nothing more should ever need to be touched on Grandpa's computer.
On our own computer, we do command-K in Finder (Go menu -> Connect to Server) and type in vnc://123.456.789.012 or whatever Grandpa's IP address is. We log in using Grandpa's name and password for his Mac.
Finally, his IP address is likely fairly static but in case it ever changes, we installed this on his computer:
That way he should be able to easily read us his IP address from his menubar and enable us to take control again.
PS: This is much faster than Copilot.com (presumably logmein.com is similar to copilot, having to route all the network traffic over http or whatever). We actually used Copilot to do all the above setup on Grandpa's computer though.
PPS: At some point the local IP address changed from 192.168.1.104 to 192.168.1.100 so we had to go back into the router's port forwarding settings (did this with copilot.com again!) and update it. Direct link for Linksys WRT54G: 192.168.1.1/Forward.htm