I think they should let us see tvOS apps in the App Store on our iPhones, even allow us to purchase or get them using our phones and have them automatically download to the AT. I can buy a game from the PSN store while at work and it will already be on my PS4 when I get home, some thing similar to that should be available with the Apple TV.
I assume it's coming. A Categories section is shown in the demo in September and it's mentioned in the user guide (in a weird way that reflects that they disabled it). If I had to guess, they were concerned about people clicking on a category and seeing only one or two apps. So I suspect that once they get over a certain number of apps that will take care of itself.