As I had mentioned in another thread, the very first thing that should be looked at is the MySQL configuration. If it's not properly tuned for your specific server specs then performance is going to be pretty bad as the database size grows.
For starters I'd use
mysqltuner to check your configuration and current variables/stats.
