A few words on app stores: My comments earlier were not directed solely at the Windows Store but were general to all the stores. I don't think anyone has a handle on managing their apps or making them sufficiently findable, it's always hit or miss to a complete disaster.
I'm not sure how you browse half a million to millions of apps, I think you don't. Categorization and more categorization plus filtering, filtering, filtering works on most things I want to buy however, most things I buy don't have millions of choices.
I see absolutely no point in mixing games with any other type of app though, that's just stupid. If I'm looking for games I should not get anything that's not-a-game in my search and vice versa; same goes for browsing. The very first choice should be games or not-a-game. Then maybe crap or not crap
of course one mans crap is another mans treasure... maybe simple (1-5 functions), basic, moderate, advanced, expert levels might help.
Categorization:
If I select a category and you cut off the list at 1000 the category needs subcategories not to mention I might not be shown the app I really wanted if I could only get to it. If there are 25 categories and each is limited to displaying 1000 then can I only find 25,000 apps? What about the other 450,000 or more?
If I search in a category only show results for that category.
You probably don't want more than 3-5 levels of categorization but I could be wrong about that.
Filtering options, give us lots and lots of filtering options including custom filtering and keyword filtering i.e. each filtering choice allows me to define the parameters or a keyword.
There's a lot more: TL;DW (Too Long; Didn't Write).