Really? There have been several features shot in recent years on super 16mm, scanned at 2K, and shown on the big screen (in both 35mm and DCP). They look just splendid, certainly a lot better than SD video could ever provide.
So I really don't think HD would be overkill for 16mm 500T, but even if I end up using a slower stock like you suggest, my original question remains: I need a lab. :) Any suggestions?