Find all dirs/files that have symlinks pointing to them

What you are looking for might be qfile. It is part of app-portage/portage-utils package and provides option -o or --orphans. You can use something like

find /usr/bin | xargs -I{} qfile -o {}

to get a list of orphaned files in /usr/bin.

Remark: Sadly, qfile in the current stable version of portage-utils, does not support readin from stdin, and the solution mentioned in the man page of qfile qfile -o $(find /usr/bin) does not work if the find result set is large, therefore we have to work around it a little bit, using xargs.

BTW, this is not something I myself came up with, but I found it at gossamer-threads, a comment by yvasilev.

What you're asking for doesn't make much sense in the general case, so it's not surprising that find has no provision for it.

A symlink with a relative target is relative to the path of the symlink. So for instance, if by traversing a directory by following symlinks, find encounters a/b/c/d and a, a/b, a/b/c are all relative or absolute symlinks (or symlinks to paths with symlink components), what should it do?

If you're looking for a find predicate or a GNU -printf % directive that expands to a symlink-free path to the file relative to the current directory or any directory, I'm afraid there's none.

If you're on Linux, you can get the absolute path of those files with:

find -L foo -type f -exec readlink -f {} \;

As you found out, there exists at least one realpath command which accepts more than one path argument which in combination with the standard -exec cmd {} + syntax is going to be a lot more efficient since it's running as few realpath commands as necessary:

find -L foo -type f -exec realpath {} +

find -L foo -type f -print0 | xargs -r0 realpath

might be quicker as if more than one realpath command is needed, find can keep on looking for more files while the first realpath starts working which even on a single processor system might make it more efficient.

-print0 and xargs -r0 are not standard, come from GNU but are found in a number of other implementations like most modern BSDs.

Zsh has builtin support for it:

print -rl foo/***/*(-.:A)

If you don't care about the sorting order, you can disable sorting and make it a bit more efficient with:

print -rl foo/***/*(-.oN:A)

If you want to convert those to relative paths to the current directory, you could have a look at that SO question.

If you know that all those files have an absolute canonical path (whose none of the components are symlinks) inside the current directory, you can simplify it to (still with zsh):

files=(foo/***/*(-.:A))
print -rl -- ${files#$PWD/}

Though short and convenient, and works whatever character filenames contain, I doubt it would faster than find + realpath.

With the Debian realpath and GNU tools, you can do:

cd -P .
find -L foo -type f -exec realpath -z {} + | 
  gawk -v p="$PWD" -v l="${#PWD}" -v RS='\0' -vORS='\0' '
    substr($0, 1, l+1) == p "/" {$0 = substr($0, l+2)}; 1' |
  xargs -r0 whatever you want to do with them

As I realise now, there's now a realpath in recent versions of GNU coreutils, which has the exact feature you're looking for, so it's just a matter of

find -L foo -type f -print0 |
  xargs -r0 realpath -z --relative-base . |
  xargs -r0 whatever you want to do with them

(use --relative-to . instead of --relative-base . if you want relative paths even for files whose symlink free path doesn't reside below the current working directory).