Efficient pagination for big tables
The key to performance is a matching multicolumn index of the form:

CREATE UNIQUE INDEX ON people (firstname, id);


UNIQUE, since sort order can be ambiguous without it, and you can get arbitrary results from peers.

A UNIQUE or PRIMARY KEY constraint serves as well.

While the first column is checked for equality like in your example (or sorted in the same direction as the query), this index is good for paging up and down, though it's a bit better for paging up.

With the index in place (and after running ANALYZE on the table), you won't see sequential scans any more (unless your table is small). The database is not "going through almost all your rows" any more.

Read the fine presentation by Markus Winand you are linking to. 

If you want paging across more than one firstname, use ROW values. Example for paging down:

SELECT *
FROM  (
   SELECT id, firstname, lastname 
   FROM   people
   WHERE  (firstname, id) &lt; ('John', 6)  -- ROW values
   ORDER  BY firstname DESC, id DESC 
   LIMIT  3
   ) d 
ORDER BY firstname, id;


Related:


Optimize query with OFFSET on large table


If the SELECT list only adds lastname like in your example, you might try to add that column to the index to get index-only scans out of it:

CREATE UNIQUE INDEX ON people (firstname, id, lastname);


Index expressions in this order. 

The upcoming Postgres 11 allows indexes to INCLUDE columns, which results in smaller index size, better performance and is applicable in more situations. Like:

CREATE UNIQUE INDEX ON people (firstname, id) INCLUDE (lastname);