I have created a new summary table, level_rank:
CREATE TABLE `level_rank` (
`lid` smallint(5) unsigned NOT NULL,
`cutoff` mediumint(8) unsigned NOT NULL,
`rank` mediumint(8) unsigned NOT NULL,
PRIMARY KEY (`lid`,`rank`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1
and populated it with the 1000th, 2000th, etc best scores for each level. Then I modified my score_rank function to find the lowest cutoff in this table still greater than the player's score. Then, return rank=level_rank.rank + count(*) between cutoff and score.
Hope that makes sense. It brings my query time down to about 0.20 seconds, and more importantly, drastically reduces the worst-case time (where a player has played many levels, but has a relatively poor score in each).