Reading about this issue further in the FAQ, it seems that I should ensure that Postgres has adequate and accurate information about the tables in question by regularly running VACUUM ANALYZE, something I don't do currently.
I disabled SeqScan as per the FAQ, and it indeed was a lot slower so Postgres was making the right choice in this case.