Your fire stick 4k lags? Better buy the newer model, I am using the one which is about 1.5 years old and no lag.That makes all the difference. Have mi 4k at moms place and airtel xstream box android TV at my home. Both were fast but within a month, they lag so much that it is a major pita to use them. If apple TV can remain lag free for year or two, better pay more and get that one.
Also not all android tv are going to be the same especially not the one as inferior as airtel xstream box. If you don't want to buy a fire tv for some reason and want to spend 20k, you can go for the nvidea shield pro and that will not lag. Even fire stick as I said hardly lags and it is 1/3 the price of apple tv or Nvidia shield