Never mind, figured it out! Copied the icon.library from the Aminet archive and the LoadResident command from the author's demo ADF that I found a link to on EAB, and then added these lines to the very beginning of my Startup-Sequence:
Version >NIL: icon.library 46 REVISION 4
IF WARN
IF EXISTS LIBS:workbench.library
LoadResident >NIL: LIBS:workbench.library
EndIf
LoadResident >NIL: LIBS:icon.library REBOOT
EndIf
...I'm guessing the workbench.library lines are for people who actually have a workbench.library (4000T owners? Or maybe if they're using some modified version that I think the author is also working on?), dunno but I left them in there. And the rest did the trick! And yes, definitely an improvement on speed, and nice to be able to see NewIcons images now instead of just the little square without having to install NewIcons or a bunch of other cr@p. Just wish I hadn't had to beat my head against a wall for two hours to figure it out.

Ah, Amiga programmers. Making you have to actually work to get anything installed, since 1985.
