The awesome guys at Flickr just added options to the "sort" parameter of the flickr.photos.search method that allow you to sort by "Interestingness". Right now, this is undocumented on their site but it should be out some time on 10/21. In case you want to start using this right away, if you specify "interestingness-desc" or "interestingness-asc" in the sort field, you'll get photos sorted by interestingness. I already have an example up for how you can use this with phpFlickr.
I'll probably be putting out a new update in a few days for a few minor bugs and to implement a few minor changes in the API.