It depends on local factors and actual usage patterns. Bigger queries require more memory to store the data and potentially, depending on the plugins you use, to process it into the response, therefor you are more in a risk of running out of memory. With Bigger response (i.e. bigger page HTML) it takes more time to transfer the page to the browser making the page feel as if it is slow loading for people on low bandwidths.
Those are the reasons why people are wasting time on a "load more" and infinite scroll mechanisms, but since technology gets better and faster all the time I don't think it is possible to give a number that can serve as a threshold to decide when AJAX is a must and not just "nice to have".
The UX perspective might be the most important factor to decide between the two. If those posts are articles to be read by humans then even 20 might b too much, but if it is a spreadsheet you probably will want to load it all in one go.
EDIT
I missed the most important part of the question which is the randomness. For sure randomness and paging do not play nicely together although you can force them to, but an easier way to achieve randomness is to query all the posts and store in an array, randomize the array and store it as a transient for one hour.
$posts = get_tranient('my posts');
if (!$posts) {
$posts = get_posts(your args);
shuffle($posts);
set_transient('my posts',$post,HOUR_IN_SECONDS);
}
... slice the part of $posts you are interested in and work on it ...
There is still a hole in this logic when you serve a page on the hour boundary, but realistically no one is going to notice some overlapping results once an hour.
On the bright side it means that you will run a slow query only once an hour and not for each request.
As for the updated part of the question, I never tested it myself but memory size is not linearly related to the size of text in the post itself and you need to factor the meta data associated with the post, and then there is the non persistent memory cache that might basically double the memory usage (there should be a way to prevent caching but I can't find it now).
While it might be that you can serve all the 300 quotes at once , there is very little point in that, even in serving more via AJAX, as humans just not going to read so much "aside" text.