Since you're only processing child directories (immediate subdirectories), a shell loop may be the simpler solution:
(cd "/path/to/dir" && for d in */; do sudo tar -zcpvf "${d%/}".tar.gz "$d"; done)
I know you want to avoid cd, but by enclosing the entire command in (…), it is run in a subshell, so the current shell's working dir. remains unchanged.
The remainder of this answer discusses how to solve the problem using GNU find.  
The -execdir solution would work with BSD/OSX find too, and would actually be simpler there.
As for getting find's -printf to only print the filenames, without any directory components: use the %f format specifier:
find /path/to/dir/* -maxdepth 0 -type d -printf "%f\n"
This will print the mere names of all immediate subdirectories in the specified directory.
However, what you print has no effect on what {} expands to when using the -exec action: {} always expands to the path as matched, which invariably includes the path component specified as the input.
However, the -execdir action may give you what you want:
- it changes to the directory at hand before executing the specified command 
- it expands - {}to- ./<filename>- i.e., the mere filename (directory name, in this case), prefixed with- ./- and passes that to the specified command.
 
Thus:
find /path/to/dir -mindepth 1 -maxdepth 1 -type d -execdir sudo tar -zcpvf {}.tar.gz {} \;
Caveat: -execdir only behaves as described for files that are descendants of the input paths; for the input paths themselves, curiously, {} still expands to the input paths as-is[1]
.  
Thus, the command above does not use globbing (/path/to/dir/*) with -maxdepth 0, but instead uses /path/to/dir and lets find do the enumeration of contained items, which are than at level 1 - hence -maxdepth 1; since the input path itself should then not be included, -mindepth 1 must be added.
Note that the behavior is then subtly different: find always includes hidden items in the enumeration, whereas the shell's globbing (*) by default does not.
If the ./ prefix in the {} expansions should be stripped, more work is needed:
find /path/to/dir -mindepth 1 -maxdepth 1 -type d \
  -execdir sh -c 'd=${1##*/}; sudo tar -zcpvf "$d".tar.gz "$d"' - {} \;
Involving the shell (sh) allows stripping the ./ prefix using a shell parameter expansion (${1##*/} would, in fact, strip any path component).
Note the dummy argument -, which the shell assigns to $0, which we're not interested in here; {} then becomes shell parameter $1.
[1] With ./ prepended, if an input path is itself relative; note that BSD/OSX find does not exhibit this quirk: it always expands {} to the mere filename, without any path component.