How to structure the database - MYSQL performance question

Could some of these issues be overcome by careful use of indexes (another area in which I am a complete novice)?

Absolutely. You should create the appropriate indexes depending on the queries that you'd execute, and the same goes for performance optimizations via restructuring.

You can't optimize the data itself and by itself for anything else than size, which you already know as normalization. Not knowing what kind of lookups you'd be doing on it, we can't give you any meaningful advice on how to structure it.