Yes, sorting by downloads ensure that most "well known and useful (certainly ?)" plugins are shown before others, like it's generally done in most places, but (as Marina said) making new plugins (things in general) hard to be "visible" and to make their place.
I also like sorting by new release, that would encourage (theorically) people to update and make better versions.
Of course, each method can be abused : making small updates with nearly nothing in it, but also (self) downloading very regularly, or (self) rating...
Perhaps sorting with a mix of most downloaded and newly updated could be a good idea ?
PS : i think this thread would better be in Moodle community sites forum.
Séverin