Depending on the available memory try increasing the shared buffers and work_mem and see if that changes the query execution time. Also make sure you have proper indices created and also if possible try doing partitions for the table.
Once you post the EXPLAIN ANALYZE output that will certainly help solving the problem...
Have you run vacuum and analyze on the table? What version of Postgres are you running? What OS are you using?
This looks like a straight forward query. With any database the first time you run the query its going to be slower because it actually has to read off disk. The second time its faster because some or all of the data/indexes will be cached. However 10 seconds sounds like a long time for pulling 10,000 records out of a table of 3 million. If you post an EXPLAIN ANALYZE, it might give us a clue.