>I build this wonderful setup that does a lot of things. It contains three EXE, including two Windows Service. Everything works ok. I tested that on my PC and all is fine so far. When I try to install that on a client site, a prerequiste requires .NET Framework 4.0. So, Setup.exe complain saying that 2210 MB is necessary. I only have left 870 MB. But, outch, I almost have 1 GB left and Setup.exe wants more.

That sounds odd. On my machine the full v4.0 framework (including temporary files that get added during use) is less than 400mb. But that includes versions for all platforms, WPF libaries etc. - you should be able to supply *way* less than that:
http://www.hanselman.com/smallestdotnet/

Does this mean I have to change my project to have those 3 EXEs to require .NET Framework 4.0 Client Profile instead? When doing so, as soon as I build, I end up with hundreds of errors as the environment cannot load pratically anything. So, what is the proper way of doing this?

I believe Client Profile excludes most ASP.NET stuff. Although you get 'hundreds' of errors they *might* boil down to the use of just one excluded DLL or just a small bit of functionality that could be achieved differently.....