Sounds like you have a 4GB QC. This can be inefficient when it locks the QC and does a linear scan of the entire QC. The lock blocks (I think) all SELECTs. Wait awhile -- see if the QC is used much, and if the hit ratio is high. Also check the size limit of the resultsets that it will save:
http://dev.mysql.com/doc/refman/5.0/en/server-system-variables.html#sysvar_query_cache_limit
Your result sets are rather big, yes? They may not be cached.
A single select will effectively use only 1 core. Multiple selects running at the same time will use separate cores, but will block on the QC and key_buffer.
(The OPTIMIZE is redundant with the ALTER.) (The ALTER TABLE probably did very little, since the data was already inserted in that order.)
I'm not a fan of partitioning, but it might be beneficial here. I would pick whichever of x,y,year,month usually has the least values.