First of all, I come across the eval { require $somepm; }; quite often and the eval will be executed regardless of whether a module has already been required. This is slow.

No, eval is not "slow" in this case. Perhaps you are confusing eval { BLOCK } with eval "STRING".