Inserting an icon from your server shouldn't slow anything down appreciably unless your readers are connected to the internet by an old cocoa tin and a piece of string ... an icon should be under 1KB, so there's no problem with download speed. What might be a problem is that many email clients don't automatically show 'remote content' (ie images that are not included with the message), so it could look messy if they get an email that has lots of missing images, until they click the "show remote content" option.
Inserting an icon automatically with CSS still has to download the icon from somewhere, and that somewhere is probably your server. There are two ways to do it, one is to set a background image on the link/class and give it a bit of padding, so that the icon shows up to the side of the link text, and the other is to use content:after (generated content) to add an <img> element. Neither of these are likely to work well in more than a handful of email clients. Outlook 2007 certainly won't render background images, and I would be astonished if it shows generated content. On that basis, manually inserting an icon after relevant links is far and away the most reliable and robust method for email.