Ordering the products i 5 different ways, and then selecting a random order-method is not good (the pick was almost static among my ~25000 products)

Use rand() in the SQL call:

tep_db_query("select p.products_id, p.products_image, p.products_tax_class_id, if(s.status, s.specials_new_products_price, p.products_price) as products_price from " . TABLE_PRODUCTS . " p left join " . TABLE_SPECIALS . " s on p.products_id = s.products_id where products_status = '1' order by rand() limit " . MAX_DISPLAY_NEW_PRODUCTS);

I have attached my rnd_products.php (zipped)

More...