Si può fare "tutto"... bisogna solo decidere come farlo.

Opzione uno: si creano i file delle thumbnails prima, a parte (via php, a mano, come preferisci), il random si fa su quelle e opportunamente si va ad aprire in un'altra pagina l'immagine originale.

Opzione due: si crea al volo la thumbnail, via php. Elegante ma considera che giochicchiare con le immagini è un thread "pesante" e nel caso in cui avessi diversi visitatori contemporaneamente, il tuo servizio hosting potrebbe tagliarti le risorse. Per ottimizzare il tutto, si potrebbe pensare ad un sistema di caching delle thumbnails già create... ma a questo punto, tanto vale rifarsi alla opzione uno.

Opzione tre: niente thumbnails, ossia, la thumbnail è semplicemente la versione dell'immagine con i parametri height e width opportunamente scalati. Il vantaggio in questo caso è che carichi il file una sola volta... lo svantaggio è che la thumbnail non è una vera thumbnail, e gli utenti col modem a 56K (o anche gli impazienti con linee veloci...) non ti ringrazieranno di certo.

Saluti.

PS: per le soluzioni php, fai un giro nella sezione php del sito, se n'è parlato in lungo e in largo. In particolare leggi i tutorial e gli articoli sulle librerie GD. Una ricerca preliminare sul forum altresì ti fornirà decine di spunti di programmazione.
Ciao