To sum up all the discussion in the comments, and not to change my initial proposal, this is what I'd come up finally:
You want to access images via tags; each tag relates to a set of images. As a given tag may be used a lot more than another (say, New York photos used a lot more than Chicago's), you should use a RESTful configuration that allows caching, so you can cache New York photos. IMHO, the solution would be:
Each image has a fixed URI:
http://www.example.com/images/12345
Each tag has also a URI:
http://www.example.com/tags/New_York/random
This URI acts as a random dispatcher of images on the set; it returns a 303 See Other response, redirecting to a random image of the set. By definition, this URI must not be cached, and the fixed one should, and the browser shouldn't understand that the redirection to the second resource is permanent, so it's optimal.
You could even access the whole set via:
http://www.example.com/tags/New_York
This access would result in a 300 Multiple Choices response; it returns the whole set (as URIs, not as images!) to the browser, and the browser decides what to do with it.
You can also use intersection of various tags:
http://www.example.com/tags/New_York/Autumn/Manhattan/random
http://www.example.com/tags/Autumn/Manhattan/New_York/random (equivalent to the previous one)
http://www.example.com/tags/New_York/girls/Summer/random
etc.
So you have a fixed URI for each image, a fixed URI for each tag and its related set of photos, and a fixed URI for a random dispatcher that each tag has. You haven't need to use any GET parameters as other potential solutions, so this is as RESTful as you can get.