One of my biggest problem with the fire tv stick was to find the apks of the android tv version of an app, which usually isn't the same apk that you have installed on your phone (and are impossible to find ). I found this app called YalpStore that basically lets you download apps from the play store as an android tv device and doesn't require Google play services.
How to use:
-Download the app from xda labs and sideload it on your fire tv
-Open the app, click on the menu button on your remote and select "search"
-if asked, select "log in without google account"(experimental)
-to navigate inside the app, you may need the "mouse toggle" app to emulate a mouse pointer (or a Bluetooth mouse)
Install the apps and enjoy
Link from xda labs:
Hope it is useful