The dreaded is_private column :)
I don't know that there's an efficient way of doing what you're looking for without adding some extra columns to your schema. You could assign a random number to each image, then order by that (faster than ORDER BY RAND(), since it's not computed each time). You could add an upload timestamp, then order by (say) seconds * 60 + hours; although that looks strange, it should prevent clustering of same-upload images (supposing that parsing an image takes at least 0.5s, which is a somewhat reasonable assumption given current upload speeds and image file sizes). You could invert the index column (as in, string reversal) and order by that.
None of these fundamentally change the concept, but to get them to work quickly you'd need to alter your schema.
Have you considered modifying your presentation? Maybe a sample of a user's most recent (highest id?) images, followed by the necessary "read more below the fold." Something like:
[img_1/kyle] [img_2/kyle] [img_3/kyle] "See all of Kyle's 50 pix"
[img_1/jan] [img_1/soulmerge] [img_2/soulmerge] [img_1/jason]
[img_2/jason] [img_3/jason] "See all of Jason's 72 pix"
Just a thought.
Edit: based on your comments, if you'd like to display the most recent on a per-album basis, well, it's highly database-dependent; I think some databases make this easy, but MySQL definitely does not. Here's an example of a way to accomplish this (in MySQL 5.0+):
SELECT
i.id,
i.user_id,
i.title
FROM
foto_images i,
(
SELECT
foto_albums_id,
MAX(id) AS image_id
FROM foto_images
WHERE foto_albums_id <> 0
GROUP BY foto_albums_id
) tmp
WHERE
i.foto_albums_id <> 0
AND i.foto_albums_id = t.foto_albums_id
AND (
SELECT COUNT(*)
FROM foto_image
WHERE
foto_albums_id = i.foto_albums_id
AND id BETWEEN i.id AND t.image_id
) < @NUMBER_OF_PREVIEW_IMAGES_TO_SELECT
ORDER BY i.id;
Note that, somewhat dependent on your indexing and amount of data, this query can be highly inefficient. Possibly consider warehousing the information? An extra column, display_on_main_page, defined at upload termination?