There may be a substantial impact on the first few queries after the rows were deleted, because autovacuum hasn't finished processing the table yet and queries need to dig through a lot of index entries that belong to deleted rows.
However, these index scans will mark the index entries as "dead", and subsequent index scans will ignore them.
REINDEX INDEX didn't work because PostgreSQL checks the index owner (which is rdsadmin).
However, REINDEX SYSTEM and REINDEX DATABASE only check the database owner (which is myself).
REINDEX SYSTEM <database>
fixes the issue.