I could think of a couple ways that might make your query faster without caching. By ordering on rand(), you are forcing a table scan of the entire post and thread tables, because that is the only way mySQL can use to determine which row will be ordered first.
So, the first option I see is to limit the posts by the dateline field. After all, do you really want a random post from any time in your board's history? You might limit it instead to a certain number of days in the past.
The second option, is to take advantage of MySQL's super fast row counting on MYISAM tables. You'd use two queries to get your result. The first would do a count of the rows. In PHP, you'd then randomly determine which one you wanted to use. Then execute a second query that used LIMIT $randomRow, 1. That would look something like this:
PHP Code:
// get post count
$posts = $vbulletin->db->query_first("SELECT count(*) total_posts FROM ".TABLE_PREFIX."post");
// determine a random offset point. Offset starts at 0, so subtract 1 from result
$randomRow = rand(1,$posts['total_posts']) - 1;
// Retreive the row
$Qrs = $db->query_first("
SELECT pagetext, username, p.dateline, t.title, p.postid
FROM ".TABLE_PREFIX."post p
INNER JOIN ".TABLE_PREFIX."thread t on t.threadid = p.threadid
LIMIT $randomRow, 1
");
// The rest of your code.....
(Note I just wrote this up in notepad, I didn't test it. But, I think this should work for you.)