Behold the GeoURI:
It’s just a simple lat/long pair which some browsers (mostly mobile) will parse as locations. It probably won’t work in your desktop browser, but here’s an example as a link: Askinosie Chocolate — Springfield, MO.
You can encode case-insensitive URIs very efficiently as QR Codes. If you’re okay with ~10m resolution on your locations, you can make very tiny QR Codes indeed:
qrencode -i -o Askinosie.png 'geo:37.2298,-93.2866'