To make an exe then, yes, you do need a compiler. The one included with visual studio express will do it, though you won't be able to compile FRED with it, as will gcc if you're running linux.
C is sort of an intermediary language, making it a bit more complex than a true high level language, but I wouldn't call it too advanced. I know several people whose first true programming language was C. If you know any Java, that might even make it easier to get started, as the syntax is similar in many ways. Perhaps the big thing about C is that it lets you make mistakes - You are given power to do stuff, but with that, you are also given the power to mess things up horribly.