You are using the Caoraline theme. That theme is coded to display blue links with red as a hover color. When links are clicked thry change color to black. All browsers display links in slightly different ways. What you describe is notmal behavior for your theme.
Also would love the links not be blue at all. Is that possible?
Yes. If you have CSS editing experience, you can get the paid custom CSS upgrade and renew it annually. It will allow you to stylize the appearance of themes you find here > Appearance > Themes, but it does not allow you to change the functionality, by editing the underlying template. Also note that CSS is theme specific, so you cannot use the CSS stylesheets from other themes with the themes here at wordpress.COM.
Since there is no official Staff support for the CSS upgrade, and precious little Volunteer support, I recommend that you don’t buy the upgrade unless you have at least moderate understanding of HTML and CSS because you must be prepared to do the work on your own.
If you are considering purchasing the upgrade, you can go to Appearance > Edit CSS. There wordpress has provided a preview function where you can try before you buy.
tutorials, tools and resources are found here > http://en.support.wordpress.com/custom-css/#css-help
If you do purchase the upgrade be sure to read this article before starting your editing > http://csswiz.wordpress.com/2009/10/15/if-you-have-the-wp-com-css-upgrade/