Yes, USE RESOURCE HACKER.
What you're doing ATM, is basically just changing the icon of the shortcut. If someone actually looks at the EXE, then they can see 'the boring grey silver thing'.
With Resource Hacker, you can actually CHANGE the icon of the EXE.
Also, icons are normally 16x16, 32x32, and 48x48 in size (you can have more than one icon size in an ICO file).
But, you can tell Windows to use a stupid size like 15x15 or 20x20 (look in Desktop Settings), and everything looks stretched....... apart from your EXE, if you made your icon this size.
How's my typing? Phone 0800-GO-TO-HELL