How many different types of links are there on the seeUthere site?
Some are underlined, some are not. Some are red, others are blue, still others are dark blue. Some are larger than others. There are way too many link styles going on.

How can a user immediately recognize a link on the seeuthere site? By the traditional means of underlining or that familiar blue color? They can't. The only way is for them to learn to recognize the various link styles after spending some time at your site. That's what you want to avoid.
And how can I tell which links I've already visited?

On most sites blue indicates an unvisited link, red or a darker color indicates a link that you have already clicked on. You can try to be creative, but this is the basic structure that most users are used to seeing. You can help out users right here by adhering to this standard. It's there for a reason.

Whatever you decide to use as your link look and feel, make sure that you use it consistently. Don't confuse the user! Have you ever clicked on something that you thought should be a link, but wasn't, or searched all over a page for a link, only to realize that there was a piece of rather ordinary text that was actually a link, but underlining was turned off so it was not easily recognizable? It's not the end of the world, but it wastes your time and is frustrating.

What is the color structure of the links on the homepage communicating design-wise? Why exactly are there so many different types? There appears to be some message to the different colors, some reason why they are different, but what is it?

I recommend standardization of all links (with the possible exception of the navbar links, since these are obviously and clearly different to the user. It's apparent why they look different and turning off underlining does help readability in this case).

All links in the page body should be underlined, in some shade of blue, which is most recognizable to users as a link. All links should show visited status with either a dark blue or red. This standardized use of color and underlining helps users greatly in navigating through the site by enabling them to identify links quickly and easily.

See Sin 5 of Drue Miller's Seven Deadly Sins of Information Design for more on the importance of link color standards.