While i do like the default search being newest, i think itd be super nice to have a random option!

Second, random shop would be nice

agreed, since it's sorted by most recent approved item by default, often the first shop in the list hasn't been updated by the user, and might have no items listed at all or just nothing new that you can see. I think it'd be nice if the default was a random order, with those that have at least one item in stock listed before those that don't