Android TV has a serious app discovery problem, and it's the built-in "leanback" version of the Google Play Store. Before today, the Play Store on your TV only showed curated apps selected by the powers that be at Google, so between the video, audio, and game sections, there were less than two hundred apps on display for users. You might get the impression that these were the only Android TV apps available - the rest had to be manually searched for in the search function of the main leanback launcher.
With version 5.5.15, that finally changes. New sections of the Android TV Google Play Store are now visible beneath the curated portion, and based on a quick run-through, it looks like every compatible app for your ATV device is exposed. You can scroll through lists of hundreds and hundreds of categorized results, just like on the main page of the Play Store on your phone or tablet. Based on several root tools, fart apps, and location-specific video streaming apps, there's no way these are being manually selected by Google.
In addition to the Top Apps list, standard apps are further divided into Messaging, Photography, Media, and Tools & Utilities. (Note: sometimes developers mark their apps incorrectly - the fighting game Soul Calibur is the most-downloaded "Messaging" app for Android TV, for example.) Games are further divided by genre, such as Arcade, Casual, Racing, et cetera.
The update should go out automatically to all Android TV devices, but the improvement in app discovery and browsing may inspire you to install the APK manually. This is a little tricky for Android TV: you'll need to enable sideloaded apps in Settings, just like an Android phone, then find a way to get the file onto the device itself. The easiest way I've found is to drop the APK onto Google Drive or Dropbox, then use the cloud storage function of ES File Explorer (a free download for Android TV already available in the Play Store) to manually load and install it. If your device supports external storage, like the SHIELD TV or the Android M developer preview build of the Nexus Player, you can just drop it on an external drive.
There may be other changes to the new Android TV Play Store, but since Google doesn't release update notes for Play Store in a user-accessible way, we haven't been able to find anything else of note. If we do, this article will be updated.
Download
The APK is signed by Google and upgrades your existing app. The cryptographic signature guarantees that the file is safe to install and was not tampered with in any way. Rather than wait for Google to push this download to your devices, which can take days, download and install it just like any other APK.
File Name: com.android.vending-5.5.15-leanback-80300195-minAPI21.apk
Version: 5.5.15-leanback (80300195)
MD5: d6bbf9f107d0276fbfa5979100175795
Thanks: Shane Menshik