How do I run a binary linked against a shared library without using LD_LIBRARY_PATH or rpath?

This has been bugging me for a while. I tried linking a shared object to an executable in one of my projects (structured like this):

.
├── lib.c
├── lib.h
├── main.c
└── Makefile

...using this Makefile:

CC != if command -v clang; then continue; elif command -v gcc; then continue; else echo c99; fi

.PHONY: build

build: main
    ./main

lib.so: lib.c
    $(CC)  -shared -fPIC -o lib.so lib.c

main: main.c lib.so
    $(info Building executable: "main")
    $(CC) -o main main.c lib.so

...but then I got this error: ./main: error while loading shared libraries: lib.so: cannot open shared object file: No such file or directory

I did find some existing solutions, involving the use of the LD_LIBRARY_PATH variable or the -Wl,-rpath=path/to/dir compile flag, but let's just say that I want another way of fixing this problem.

I know, just hear me out. I've been able to successfully run binaries linked to a shared object in a hierarchical structure, like so:

.
├── bin/
│   └── main
├── lib/
│   └── lib.so
├── src/
│   ├── lib.c
│   ├── lib.h
│   └── main.c
└── Makefile

...and I didn't need to use either method. I also used ldd on the binary in the above example:

$ ldd bin/main
    linux-vdso.so.1 (0x00007ffec55e7000)
    lib/lib.so (0x00007f3198a7f000)
    libc.so.6 => /usr/lib/libc.so.6 (0x00007f3198876000)
    /lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007f3198a8b000)

In comparison to the troublesome binary:

$ ldd main
    linux-vdso.so.1 (0x00007ffc2de5f000)
    lib.so => not found
    libc.so.6 => /usr/lib/libc.so.6 (0x00007880524c3000)
    /lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007880526d3000)

While I might be making an assumption here, I will not pretend that I haven't found an answer to this question yet. I will be posting my own solution not long after I have posted this question.

...but then I got this error: ./main: error while loading shared libraries: lib.so: cannot open shared object file: No such file or directory

1. You should not name your library lib.so. Name it something like libfoo.so (where foo represents the functionality that the library provides.
2. You should not link your main executable using the path to libfoo.so.
   Instead, do this: $(CC) -o main main.c -L. -lfoo.
3. In order to make your binary find libfoo.so at runtime, you need to encode into the binary instructions for the dynamic loader telling it where to look.
   

There are several common approaches for (3):

• Use system library directories. For this you copy libfoo.so into e.g. /usr/local/lib
• Use a fixed directory, e.g. current location. For this, add -Wl,-rpath=$(pwd) to the link line. Note that you'll need to escape $ when adding this command to the Makefile.
  
  This approach has a disadvantage: if you rename your directory, the binary will stop working.
• Use directory relative to where the binary itself was found. For this, add -Wl,-rpath='$ORIGIN'. This approach allows you to freely copy {main,libfoo.so} to a different directory and remove the original. The binary will continue to work so long as both main and libfoo.so are in present the same directory.
• Use LD_LIBRARY_PATH. This has an advantage of being easy to update if/when you moved the project directory, but a disadvantage in that you have to maintain that variable, and the binary will or will not work depending on the environment it runs in.