The nil value is a special case in Lua's tables.
Yes, nil is a semantically special value when used in Lua tables.
Does this mean that Lua should have performance problems when using it?
Do other languages have performance problems with their own special values (null/none/undefined)?
The problem with surprisingly poor performance of program #2 in the OP has at least 3 solutions:
1) To honestly claim in the manual that using nils in tables is strongly discouraged. Use false instead.
2) To honestly warn users about performance penalties of tables with nils. Introduce table.new()/rebuild() to help users improve performance when they need.
3) To fix the "not-a-bug" (bad algorithmical design of table implementation) which prevents Lua from working with nils fast.
Would you have reached the same conclusion if the problem had been
formulated in terms of true and false rather than 'Lua' and nil?
As I see, you have chosen the first option - to encourage everyone to use false.
IMO, it's not a good option. It's the worst of the three.