Should using spaces in math mode be a common thing?

Getting the spacing around \exists and \forall is tricky. Look at this example: $\forall W\forall A$ gives

Of course there should be more space after the W. More interestingly, the spacing between \forall and W is too tight, whereas between \forall and A it is maybe even a bit too loose. Why is this so?

If you use the standard Computer Modern fonts, then \exists and \forall come from the math symbol font cmsy, whereas letters like f and r come from the math italic font cmmi. Now the point is: TeX doesn't allow automatic kerning of characters from different fonts. But in order to have good spacing after \exists and \forall in all cases, you'd need specific kerning information depending on the subsequent character, as the above example shows.

The kerning information would have to be provided by the font designer, and it would have to be one font containing all the characters involved. I don't know if there are fonts where this is realized.

So yes, for the Computer Modern fonts (and probably most other math fonts) you'll have to rely on manual kerning with \, and friends to get things right. Here's an example how you could do it. Note that I use \colon instead of a :. Moreover, I define \+ which adds a space slightly smaller than \,.

\documentclass{article}
\usepackage{amsmath}
\let\eps\varepsilon
\newcommand\+{\mkern2mu}
\begin{document}
$\forall\eps>0\;
\exists\+\delta>0\;\forall x,y\in X\colon\dots$
\end{document}

Your first math expression:

\[ A_4 = \left\{ f | f(x) > g(x) , x \in [0;1] \right\} \]

looks like this when typeset with Computer Modern fonts:

This does look quite cramped.

In the TeXbook (in one of the chapters on math typesetting), Knuth proposes (i) using the command \mid instead of | when expressing a "given that" or "conditional on" thought and (ii) inserting thin-spaces after the opening left curly brace and before the closing right curly brace. It's also a good idea to insert an explicit space after the comma, to highlight the fact that f(x) > g(x) and x \in [0,1] represent separate conditional clauses. Incidentally, the \left and \right directives do nothing useful in the present example and should probably be omitted.

I.e., it's probably better to write:

\[ A_4 = \{ \, f \mid f(x) > g(x) ,\ x \in [0,1] \, \} \]

As for \forall and \exists I can't help you, but I think you are right. There is not enough free space around them. I would fix this just as Werner suggested.

But with the | I have a handy solution: Use \mid instead.