Postgres - fast way to enforce AND across multiple rows
I think you have unnecessary steps in your query, consider this:

SELECT *
FROM (SELECT
        COUNT(tag) AS numtags,
        tweet_id,
        MIN(score)      AS minscore
      FROM  core_tagusage
            WHERE tag = 'dog'
                  OR tag = 'grass'
                  OR tag = 'frisbee'
      GROUP BY tweet_id) AS ct
WHERE numtags = 3
ORDER BY minscore DESC
LIMIT 200;


and this:

SELECT
    tweet_id,
    MIN(score) AS minscore
FROM  core_tagusage
WHERE tag IN ('dog', 'grass', 'frisbee')
GROUP BY tweet_id
WHERE COUNT(*) = 3
ORDER BY minscore DESC
LIMIT 200;


I also think that running analyze on your table will help the query planner.

After playing with some fabricated data locally, I was seeing ~600K rows take ~1sec, so 10 seconds doesn't seem unreasonable (but my data was so predictable that analyze made the query planner just go for a sequential scan)