This is a very / too generic question:
Q1: What size is considered reasonable?
Any size that fits easily in the CPU cache(s) of the target platform. Otherwise it depends on the memory requirements for the algorithm in general.
Q2: What make them (in)efficient?
If the CPU data cache needs to be refreshed continuously then they may slow down the algorithm and, if you're unlucky, leak side channel information as well.
Q3: Are there heuristics to determine (without implementing anything) if a table will become interesting?
Probably not as it depends a lot on specifics of the underlying platform.
In general lookup tables are used to speedup calculations, so as long as the resulting implementation is faster, you're in business.
But note that there may be security implications when using them, all depending on what is being implemented.