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.

Assessing your IO, Memory & CPU loads is the first step - Knowing where the bottleneck is, is helpful for suggesting strategy.
Often times joins are handy when you first create your DB as it pulls your data back in a tidy normalized result. As your data grows those joins can become troublesome because you are joining multiple large tables (meaning index lookups/loops through all the pertinent indexes), plus you can be bound to a single thread. Sometimes breaking that joined query into multiple queries that leverage separate threads as well as free up memory and the number of combined index's referenced at an instant between calls can be useful. I have not used Percona however, so it may have its own functionality that mitigates these concerns.

Regardless of the number of rows tables have, it's how this data is assigned on disk (and how big that is), and then read into the applicable MySQL memory buffers that matter. The goal is to reduce the memory to disk ratio for "Hot" data. Optimizing indexes is an art. There are also many tricks, like using the right data type (INT not BIGINT), covering indexes (reduces looking at data). Depending on your queries, partitioning may help. Capturing the Query Execution Plan (QEP), learning how to read, understand and improve is necessary to solve your slow queries. http://effectivemysql.com/ has a number of introduction presentations for Optimizing SQL.