Fantastically useful plugin. Thanks for sharing.
After working with it for some time, here are a few UI-related suggestions for improvement. I'm hopeful that these are not too difficult to implement and pretty certain that most users would benefit from it.
1. Repeat the pagination below the results. Currently if you retrieve more that 12 results per page, you have to scroll all the way up again to go to the next page.
2. Include a friendly link to the FPP settings on the Media uploader page. When I first installed FPP it took me a while to discover that it is set to download the medium size only. Large or Original would be a better default I think but anyway the point is that it wasn't even clear that I could set this in the first place.
3. Show more metadata on the results page. Right now you have to "choose" an image before you get to know its size, caption, and author. Size and caption would be useful in the alt text of the thumbnail so that all you need to do is hover over it. A link to the photo and/or author page on Flickr could be in the popup window.
4. Remember the "Results per page" setting, or allow me to set a default. I find 102 the most useful; 12 by far the least useful.
5. Provide my original search in the "new search" input field so that I can easily modify it. (And here again, remember the Results per page setting.
6. Allow setting result order directly with the search query instead of in the FPP settings. That way a search can be quickly redone for a different order (e.g. relevance vs. interestingness), resulting in a better hit rate.
7. FPP nicely integrates into the new design of the media uploader in 3.5. There seems to be no need for a separate button next to the media button.
8. Related to #3, would it be possible to set a minimum size? If I'm looking for featured images and I have a theme that wants them to be at least 800px wide, it would be great to tell FPP that I want to find images larger than that only.
9. If you set FPP to use images at "original" size, occassionally it hiccups at very large files (example). WordPress manages to download it but something goes wrong with thumbnail creation and FPP displays a blank page. More graceful handling of such problems would be preferable.