Can you describe the data in the table? I can think of a few solutions, most if which are based on the data you are storing.
For example, chances are when you have large tables you are probably not doing any summarization of your data. If possible pre-compute the result and spit out the answer from a shorter table or cache (a cache which is generate at the time of the summary being generated, only useful if you often request this data shortly after it being created - doesn't sound like you needed to do this though)
Another alternative would to be consider archiving of data. Is all the data required all the time? If not then consider a means of removing data you don't need (after x period of time) or switching to a new shard / table periodically.
The other, more obvious, I would mention are to reconsider your existing indexes or partitioning your tables, if you have not done this already.
You can start manually sharding tables across servers based on a hash of some kind but your Db is still relatively small (assuming you can summarize some of your data) and should not need this yet.
