ERROR: permission denied for relation tablename on Postgres while trying a SELECT as a readonly user

Here is the complete solution for PostgreSQL 9+, updated recently.

CREATE USER readonly  WITH ENCRYPTED PASSWORD 'readonly';
GRANT USAGE ON SCHEMA public to readonly;
ALTER DEFAULT PRIVILEGES IN SCHEMA public GRANT SELECT ON TABLES TO readonly;

-- repeat code below for each database:

GRANT CONNECT ON DATABASE foo to readonly;
\c foo
ALTER DEFAULT PRIVILEGES IN SCHEMA public GRANT SELECT ON TABLES TO readonly; --- this grants privileges on new tables generated in new database "foo"
GRANT USAGE ON SCHEMA public to readonly; 
GRANT SELECT ON ALL SEQUENCES IN SCHEMA public TO readonly;
GRANT SELECT ON ALL TABLES IN SCHEMA public TO readonly;

Thanks to https://jamie.curle.io/creating-a-read-only-user-in-postgres/ for several important aspects

If anyone find shorter code, and preferably one that is able to perform this for all existing databases, extra kudos.

Try to add

GRANT USAGE ON SCHEMA public to readonly;

You probably were not aware that one needs to have the requisite permissions to a schema, in order to use objects in the schema.