View to display nodes with a random term
I would set up an argument (D6) / contextual filter (D7) to filter the view results based upon a taxonomy term, and then for the argument/filter value, select the PHP option for providing the default, and in there randomly return one of your taxonomy terms.  Without actually testing the code, I would imagine using array_rand() would make this rather trivial, eg:

$terms=array('foo','bar','baz');
return $terms[array_rand($terms)];