Artist search: I think a name search on either or both of first and last name would be fine. It is mostly to help people track down which cards an artist has done so that they can collect them for signings and such.
Format changes: This is much harder. Since the rotation dates have been all over the place throughout the years, programming in specific times when any given format rotated would be an amazing amount of manual data entry work on the front end. I'd be happy if the user did most of the work by entering the sets they want to check. For instance:
+Time Spiral +Planar Chaos +Future Sight -Champions -Betrayers -Saviors
would mean, cards in the first three sets but not in the last three.
+/-Tenth +/-M10
would mean, cards in both sets.
This is not ideal in my mind, but it is something akin to what I'm thinking about.