How do I get the users real uid if the program is run with sudo?

The easier way would be using Who am i

who am i | awk '{print $1}'

or

who am i | cut -f1 -d" "

You have two good choices...

1. Trust sudo and just use its environment
2. Make your program setuid-on-execution and then geteuid, et al, will work just fine

Update:

The setuid bit is an access right flag in the file mode that causes a program to run with the capabilities of the executable file's owner. This is how sudo(1) is able to run things as root ... the sudo program itself has this mode.

$ ls -l /usr/bin/sudo
-r-s--x--x  1 root  wheel  272384 Jun 22  2009 /usr/bin/sudo*

To make a program setuid root one might:

$ chown root a.out
$ chmod +s a.out

Needless to say, setuid root programs should be written carefully. You can setuid to a less privileged user if all you need is access to a protected directory or file.

sudo provides some environment variables to help you with exactly this case:

   SUDO_UID        Set to the user ID of the user who invoked
                   sudo

   SUDO_USER       Set to the login of the user who invoked sudo

steveayre has pointed out in the comments that the user can set these environment variables in some cases; the sudo(8) manpage includes in part:

The sudoers policy subjects variables
passed on the command line to the same restrictions as normal
environment variables with one important exception.  If the
setenv option is set in sudoers, the command to be run has the
SETENV tag set or the command matched is ALL, the user may set
variables that would otherwise be forbidden.  See sudoers(5)
for more information.

So be sure that you don't grant ALL commands to users when you need to rely upon this feature.

A Linux-specific audit_getloginuid() function provided by the auditing system may be able to help; since pam_loginuid(8) is only going to be installed for the "main" daemons (sshd, login, gdm, etc.) the audit uid will remain unchanged when sudo(8) executes.

This will require a little configuration; add:

session    required     pam_loginuid.so

to the /etc/pam.d/sshd file -- and whichever other services you allow your users to use.

Ensure pam_loginuid.so isn't loaded in the /etc/pam.d/sudo configuration file.