How can one optimize a query involving a sort and a LIKE?
Your index attempts are still futile, since the predicate

u."name" LIKE 'garr%'


is obviously the most selective one but cannot use a basic (default) b-tree index unless you are operating with the "C" locale (which is uncommon). 

SELECT *
FROM   "Users"
WHERE  name LIKE 'garr%'
AND    id &lt;&gt; 2449214
AND    hellbanned IS NULL
AND    "hellbanPostsAfterDate" IS NULL
ORDER  BY "followerCount" DESC NULLS LAST
LIMIT  3;


There are several options (also depending on the missing table definition and other information), this index should work:

CREATE INDEX "Users_whatever_idx"
ON     "Users" (name text_pattern_ops, "followerCount" DESC NULLS LAST) 
WHERE  hellbanned IS NULL
AND   "hellbanPostsAfterDate" IS NULL;


The conditions on hellbanned and "hellbanPostsAfterDate" are only useful if they exclude more than a few rows. Else, a complete index might be the better choice, since it can be used for more different queries.

Also, there is a chance the second column in the index "followerCount" won't help, since there are typically multiple different matches for the first and Postgres has to sort after all. Test a couple of typical queries with and without the second column in the index.

Details for indexes and pattern matching, including an explanation for the operator class text_pattern_ops:


Pattern matching with LIKE, SIMILAR TO or regular expressions in PostgreSQL


Aside: My standing advise is to use unquoted, legal, lower-case identifiers exclusively in Postgres.