I have both the 1st gen and 2nd gen fire tv boxes (Not Sticks) and Tablo works great on both. Like JeffD said the only real issue with speed is with the Live TV guide being a little slow. But, the Tablo is not meant for Live TV channel surfing.
Sometimes, the app on the fire tv does not close properly. When you exit it'll go right back to the start up screen or live tv (if that was your last activity). When this happens, I click the "home" button on the remote and then do a force close of the app through the settings of the fire tv. I think the engineers of the tablo are trying to correct this problem, but who knows. It's not too troublesome otherwise.
I think you'll be pleased with the Fire TV app experience for the Tablo.