The most load on mysql is the random images. If you didn't use "optimized" mod for random images, you should try it. If it's already installed then you probably would be better turn random image off completely (via includes/constants.php)
Also, you can see how much time each query takes by using these lines in includes/constants.php
define("PRINT_STATS", 1);
define("PRINT_QUERIES", 1);
define('PRINT_CACHE_MESSAGES', 1);