Combine indexes to optimize "OR" queries
Query

Note this equivalent sorter syntax for your query:

SELECT *
FROM   contacts
WHERE  'Cassidy' IN (firstname, lastname, nickname);


Resolves to the same expressions in the query tree:

  (('Cassidy'::text = contacts.firstname)
OR ('Cassidy'::text = contacts.lastname)
OR ('Cassidy'::text = contacts.nickname))


The three columns can even have different data types. The single given string literal 'Cassidy' is cast to different data types for this. Exactly like in your original query.

Index

You could use a single bloom index (after installing the additional module, once per database):

CREATE INDEX contacts_bloom_idx ON contacts USING bloom (firstname, lastname, nickname);


Especially if you have more candidate columns like this and query random combinations. Also if you are short on disk / cache memory or the index is rarely needed (so not in cache). Then size matters more and a bloom index is typically small.  

But it's better for AND-ed conditions, less so for OR-ed conditions. And the manual advises:


  This type of index is most useful when a table has many attributes and
  queries test arbitrary combinations of them. A traditional btree index
  is faster than a bloom index, but it can require many btree indexes to
  support all possible queries where one needs only a single bloom
  index. Note however that bloom indexes only support equality queries,
  whereas btree indexes can also perform inequality and range searches.


And:


  Only operator classes for int4 and text are included with the module.


For just three columns, three simple btree indexes should be faster and more versatile:

CREATE INDEX ON tbl (firstname);
CREATE INDEX ON tbl (lastname);
CREATE INDEX ON tbl (nickname);


Postgres can rather efficiently combine multiple indexes in a bitmap index scan. Related:


What is a “bitmap index”?
PostgreSQL FTS and Trigram-similarity Query Optimization




A multicolumn index like:

CREATE INDEX ON tbl (firstname, lastname, nickname);


is not very usefull for this. It happens to cover firstname as first column moderately well (not as well as a smaller index on just (firstname)). Additional columns are covered poorly. You are not looking for combinations of columns, so it's the wrong tool.