Cyclone III device utilization issues

Something is wrong, as it should never run off into the weeds like that. What compiler options are you modifying? Is it physical synthesis? (This runs later in the fitter when you set it to Normal Effort, and I'm guessing some analysis algorithm is getting lost in the weeds or something like that.) As for utilization, what you're doing is much better than taking some random design, as all designs are different and will pack/fit differently.

Perhaps take the ethernet core hierarchies, right-click and Locate to Assignment Editor, copy their name into the To column and make the assignment Netlist Optimizations = Never Allow. This basically disables Physical Synthesis on those hierarchies, and might get around your issue. (I'm assuming it's the Physical Synthesis you're talking about, but not sure).