Optimizing some queries

Hello,

My hosting company is asking frequently to optimize my website which is using WordPress because it’s “overloading” the server. If I won’t fix this issue, they will have to put it on a “quarantine server”. I’m checking everyday my slow logs and I’m having always the same thing (I guess). I removed from the DB all tables created by uninstalled plugins. I removed also all the plugin that are overloading the server with queries. I’m also using a cache plugin. These steps were good but not that enough since I still have some slow queries in the log file. Anyway, here the slowlog:

# Time: 131205 22:35:33
# User@Host: XXXXXX[XXXXXX] @ XXXXXX [XXXXXX]
# Query_time: 6.183516  Lock_time: 0.000159 Rows_sent: 379  Rows_examined: 421
use XXXXXX;
SET timestamp=1386279333;
SELECT option_name, option_value FROM wp_options WHERE autoload = 'yes';
# Time: 131205 22:36:33
# User@Host: XXXXXX[XXXXXX] @ XXXXXX [XXXXXX]
# Query_time: 61.768671  Lock_time: 0.000000 Rows_sent: 0  Rows_examined: 0
use XXXXXX;
SET timestamp=1386279393;
SELECT option_name, option_value FROM wp_options WHERE autoload = 'yes';
# Time: 131205 22:37:03
# User@Host: XXXXXX[XXXXXX] @ XXXXXX [XXXXXX]
# Query_time: 93.286015  Lock_time: 0.000000 Rows_sent: 0  Rows_examined: 0
use XXXXXX;
SET timestamp=1386279423;
SELECT option_name, option_value FROM wp_options WHERE autoload = 'yes';
# Time: 131205 22:37:03
# User@Host: XXXXXX[XXXXXX] @ XXXXXX [XXXXXX]
# Query_time: 95.438348  Lock_time: 5.071881 Rows_sent: 0  Rows_examined: 1
SET timestamp=1386279423;
DELETE FROM wp_options WHERE option_name = 'rewrite_rules';
# Time: 131205 22:37:15
# User@Host: XXXXXX[XXXXXX] @ XXXXXX [XXXXXX]
# Query_time: 32.109220  Lock_time: 20.174740 Rows_sent: 378  Rows_examined: 420
use XXXXXX;
SET timestamp=1386279435;
SELECT option_name, option_value FROM wp_options WHERE autoload = 'yes';

Can someone help me figure out what’s going wrong and what is taking so much time to be done?
Thanks guys!