>>> FWIW you still haven't explained how the upgrade was performed.
>>> That might be a very important piece of information, because the
>>> 9.4 cluster might have hint bits set and/or the data may be
>>> mostly frozen, but the 9.6 cluster may not have that yet,
>>> resulting in higher CPU usage.
>
> We upgraded the database with a pg_dumpall from 8.4.22 and then a psql < BACKUP.SAV command!
Not to miss the obvious: did you run ANALYZE after importing the backup?