I think somebody mentioned embedding only the tiles that are used. If level size is a concern, that is probably my favored solution. Levels could be played without finding the tileset needed, but you'd still need the full tileset if you wanted to edit the level.
Consider that for DOS Lemmings, a graphics set is ~30kB. Granted, Eric probably won't be storing the data quite so compactly, but these level files aren't going to be measured in megabytes.