ORDER BY random() LIMIT 1 slowness

I have a query where i just want to randomly pick out one row of the
table.  The query as I am running it looks like:

SELECT * FROM poetry ORDER BY random() LIMIT 1;

There are only roughly 35,000 rows of data and there is no way that I
have found to specify what is randomly being ordered, I assume it's
picking the primary key.  The explain output looks like:

QUERY PLAN:
 Limit  (cost=49279.75..49279.75 rows=1 width=1062) (actual
time=8503.83..8503.84 rows=1 loops=1)
   ->  Sort  (cost=49279.75..49365.68 rows=34375 width=1062) (actual
time=8503.82..8503.83 rows=2 loops=1)
         Sort Key: random()
         ->  Seq Scan on poetry  (cost=0.00..5029.75 rows=34375
width=1062) (actual time=0.12..2503.35 rows=34376 loops=1)
 Total runtime: 8526.31 msec

I have different variations on the runtime, all between 5000 and 15000
msec.  Anyone have any ideas on how to speed this up?  I've thought
about doing a count query to get the total count and then use limit 1
offset #, where offset # is a number supplied by my program, but it
would be preferred to do this in query.

Thanks,

Gavin