Slow query with large dataset in Drupal views — better to process in SQL or PHP?
Are you 100% positive that the view isn't paging in SQL?  When you turn on Query Logging in the Devel module, what do you see for your view?  I just double checked a site and am seeing (formatting is mine):

SELECT node.nid AS nid, RAND() AS random_field
FROM node node
WHERE (( (node.status = :db_condition_placeholder_0)
  AND (node.type IN (:db_condition_placeholder_1)) ))
ORDER BY random_field ASC LIMIT 10 OFFSET 0


when I am on paged view with a random sort.

I have seen the double JOIN thing before.  Often, you can adjust the view parameters and get the query to run the way you want.

Optimizing these queries is really use dependent.  I am pretty sure that both of the columns you are joining on are both indexed already.  You can try to replicate the query manually, and then EXPLAIN it, and manually improve it.  You can then implement this query in a custom block, but then you lose out on other things that Views give you.  Caching the view results, may help, too.

Keeping everything in MySQL is likely best (it is meant for heavy lifting like this), but only profiling will give the true results for your system.  Just make sure you have MySQL, Apache, and PHP tuned so that you aren't chasing the wrong problem.