It is impossible to start another process on Unix without first forking a program; the child process then calls exec to become the other program of your choice.
Not quite right. You can simply call exec() without a previous fork() to replace your current program with a new one, or a fresh run of the current one. Both are common techniques. Chained exec() is e.g. used by sudo, chroot, getty, login, massively by daemontools and frieds (see Re^3: Daemon::Control pid-files and Re^5: RFC: an(other) UNIX daemon module implementation). Self-exec() is commonly used by daemons that want to reload their configuration or just want to forget about everything they have done so far.
there is no equivalent to Win32 CreateProcess
And that's a good thing! See Re^3: Set env variables as part of a command. CreateProcess() takes more than 30 parameters, its more advanced relatives take even more. fork() needs no parameters at all, exec() takes program name and arguments, the lower-level execve() system call also takes program name, arguments and a pointer to the environment. Every other aspect of the child process can be changed between fork() and exec(), without inflating any other function to take a ridiculous amount of parameters.
Also note that you don't have to call exec() after fork(). A common use are network daemons like sshd or telnetd that fork a new process for each new connection. Another use is to create one child process per task, this happens in PostgreSQL (see Re^2: Setting $0 clears /proc/PID/environ too).
An advanced use is privilege separation: Assume you have to analyze (parse) some data passed in from the network while running as root. Call fork() to create a child process. Isolate the child process in an empty directory (chroot() or jail()), set resource limits, drop privileges, close all file handles except for a way to send your result back to the privileged process. If you run on modern *BSDs, disable all system calls that this process won't need any more. Start chewing on the data from the network. exit() with a nonzero exit code if something looks fishy. At the same time, have the parent set up a timeout that kills the child process unconditionally and forcefully (kill(child, SIGKILL)). Call wait() or waitpid() to wait for the isolated process. If its exit code is not null, assume something went wrong and do not touch the data from the network any more. Discard it, disconnect the network connection.
Try to do that with CreateProcess() and its ugly relatives!