Ruby, 76 78 bytes

+2 bytes to fix errors.

->n,r,f{(a=*0...n).product(*[a]*~-r).filter{_1.combination(2).all?{|x|f[*x]}}}

Attempt This Online!

Uiua 0.16.0-dev.1, 26 bytes (SBCS)

(Without using tuples in its own definition!)

▽⊸≡(≍⟜×˙⊞<⇡⊃⧻˙⊞^0)⬚0≡˜⊥⇡⊸ⁿ

Takes in f, r and n in that order.

pad link with tests

Explanation

▽⊸≡(≍⟜×˙⊞<⇡⊃⧻˙⊞^0)⬚0≡˜⊥⇡⊸ⁿ
                  ^^^^^^^^-- Get all numbers in base n of length r
   ^^^^^^^^^^^^^^^---------- Check, foreach, which are valid by checking if applying f to each pair (^0) returns a lower diagonal matrix
^--------------------------- Keep the valid ones

APL(NARS), 62 chars

{m/⍨∧/¨⍺⍺/¨¨↑¨,/¨{{w[⍵],¨w[↑∼/⍳¨k⍵]}¨⍳¯1+k←≢w←⍵}¨m←,¯1+⍳↑⍴/⌽⍵}

I make one error in understand the algo, I hope this is better... test:

  f←{m/⍨∧/¨⍺⍺/¨¨↑¨,/¨{{w[⍵],¨w[↑∼/⍳¨k⍵]}¨⍳¯1+k←≢w←⍵}¨m←,¯1+⍳↑⍴/⌽⍵}
  {⍺=⍵} f 3 4
┌3───────────────────────────────┐
│┌4───────┐ ┌4───────┐ ┌4───────┐│
││ 0 0 0 0│ │ 1 1 1 1│ │ 2 2 2 2││
│└~───────┘ └~───────┘ └~───────┘2
└∊───────────────────────────────┘
  >f 4 3
┌4──────────────────────────────────┐
│┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐│
││ 2 1 0│ │ 3 1 0│ │ 3 2 0│ │ 3 2 1││
│└~─────┘ └~─────┘ └~─────┘ └~─────┘2
└∊──────────────────────────────────┘
  ≥f 3 3
┌10───────────────────────────────────────────────────────────────────────────────────────┐
│┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐│
││ 0 0 0│ │ 1 0 0│ │ 1 1 0│ │ 1 1 1│ │ 2 0 0│ │ 2 1 0│ │ 2 1 1│ │ 2 2 0│ │ 2 2 1│ │ 2 2 2││
│└~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘2
└∊────────────────────────────────────────────────────────────────────────────────────────┘
  {(⍵-⍺×0)>2}f 5 2
┌10───────────────────────────────────────────────────────────────────┐
│┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐│
││ 0 3│ │ 0 4│ │ 1 3│ │ 1 4│ │ 2 3│ │ 2 4│ │ 3 3│ │ 3 4│ │ 4 3│ │ 4 4││
│└~───┘ └~───┘ └~───┘ └~───┘ └~───┘ └~───┘ └~───┘ └~───┘ └~───┘ └~───┘2
└∊────────────────────────────────────────────────────────────────────┘
  ≠f 3 3
┌6────────────────────────────────────────────────────┐
│┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐│
││ 0 1 2│ │ 0 2 1│ │ 1 0 2│ │ 1 2 0│ │ 2 0 1│ │ 2 1 0││
│└~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘2
└∊────────────────────────────────────────────────────┘

in how it seems to me

{{w[⍵],¨w[↑∼/⍳¨k⍵]}¨⍳¯1+k←≢w←⍵}

would make a,¨b where a is the element of w of index J, and b are all ements of w of index >J for J in 1..≢w. That is because "a<b<c<d" of question it seems it means

(a<b and a<c and a<d) and
(b<c and b<d)         and
c<d

Vyxal, 61 bits^v2, 7.625 bytes

ʁ↔'2ḋ⁰vRA

Try it Online!

Bitstring:

0001101101111100111010110001010011111010100011000101110001010

When in doubt, port Jelly and slap a range-coder onto the result to make it look better

☾, 15 characters

󰲥ₓ􊲆⋅y⨉→󰈲󷺹⫚2ꟿz→⋀

Here is a test suite (only contains the shorter tests because I'm lazy XD).

This is only possible because of the recent implementation of a primitive "choose" (⫚) function, which allows me to make a list of combinations of the indices.

Explanation

K (ngn/k), 33 26 bytes

thanks to @att for -7 bytes! Curried function to be called as f[g][r;n].

{'[&/,/-1_'x''/|1,\\]#+!#}

Try it online!

'[&/,/-1_'x''/|1,\\]#+!#     / x=g, r and n are arguments to the trailing #
                     +!#     / all r-tuples of integers in [0, n-1)
'[                 ]#        / Keep where ...
              |1,\\          /  Prefixes of this tuple and the tuple itself 
          x''/               /  Apply f between each value in a prefix and ...
                             /   the corresponding value in the tuple (last value of prefix).
      -1_'                   /  Remove all results of calling f on the same value
  &/,/                       /  Was the f true for all tested combinations?

Charcoal, 40 bytes

≔ＵＶＳθＮηＮζＥΦＥＸηζ﹪÷ιＸη…⁰ζη⬤ι⬤…ιμ▷´θ⟦νλ⟧⭆¹ι

Try it online! Link is to verbose version of code. Takes a string of python code (typically a lambda) as the first input and outputs the tuples in lexicographic order of their reverse. Explanation:

≔ＵＶＳθ

Input f and evaluate it as Python code, which just gives me the lambda itself as a function object at this point.

ＮηＮζ

Input n and r.

ＥΦＥＸηζ﹪÷ιＸη…⁰ζη⬤ι⬤…ιμ▷´θ⟦νλ⟧⭆¹ι

Generate all nʳ tuples of r values from [0..n), filter on those where f returns true for all pairs with ascending indices, and pretty-print each tuple.

By switching to ATO I can implement a more efficient version for the same byte count (it would normally be 8 bytes longer on TIO):

≔ＵＶＳθＮη⊞υ⟦⟧ＦＮ≔ΣＥηＥΦυ⬤μ▷´θ⟦ξκ⟧⁺μ⟦κ⟧υＥυ⭆¹ι

Attempt This Online! Link is to verbose version of code. Takes a string of python code (typically a lambda) as the first input and outputs the tuples in lexicographical order of their reverse (it is possible to output the tuples in regular lexicographic order but then the program will crash if there are no matching tuples). Explanation:

≔ＵＶＳθ

Input f and evaluate it as Python code, which just gives me the lambda itself as a function object at this point.

Ｎη

Input n.

⊞υ⟦⟧

Start with one tuple of no elements from [0..n).

ＦＮ

Repeat r times...

≔ΣＥηＥΦυ⬤μ▷´θ⟦ξκ⟧⁺μ⟦κ⟧υ

... for each element of [0..n) and each tuple so far where f returns true for all elements of the tuple and that element, create a new tuple with the extra element.

Ｅυ⭆¹ι

Pretty-print all of the resulting tuples.

Python 3, 92 bytes

f=lambda n,r,g:[[]][r:]or[a+[b]for a in f(n,r-1,g)for b in range(n)if all(g(c,b)for c in a)]

Try it online!

JavaScript (V8), 82 bytes

Expects (n)(f)(r) and prints the valid r-tuples.

n=>f=>g=(r,o=[],k=n)=>r?o.every(v=>f(v,k),--k&&g(r,o,k))&&g(r-1,[...o,k]):print(o)

Try it online!

Commented

n =>             // 1st function taking n
f =>             // 2nd function taking f
g = (            // g = main recursive function taking:
  r,             //   the last argument r
  o = [],        //   o[] = output
  k = n          //   k = counter, starting at n
) =>             //
r ?              // if r is not zero:
  o.every(v =>   //   for each value v in o[]:
    f(           //     invoke the black-box function f
      v, k       //     with v and k
    ),           //
    --k &&       //     decrement k; if it's not zero:
      g(r, o, k) //       do a recursive call to g
                 //       to try the next value of k
  )              //   end of every()
  &&             //   if successful:
    g(           //     do a recursive call to g with:
      r - 1,     //       r - 1
      [...o, k]  //       k appended to o[]
    )            //     end of recursive call
:                // else (r = 0):
  print(o)       //   we have a valid tuple: print it

Python 3, 110 bytes

lambda n,r,f:(s for s in product(*[range(n)]*r)if all(f(*a)for a in combinations(s,2)))
from itertools import*

Try it online!

combinations seems like a long word for code golf but here we are.

@Lucenaposition I did steal your idea inside product which saved 4 bytes vs using repeat=r.

Python 2, 124 bytes

lambda n,r,g:[x for x in product(*[R(n)]*r)if all(g(x[a/r],x[a%r])for a in R(r*r)if a/r<a%r)]
from itertools import*
R=range

Try it online!

Jelly, 9 bytes

ṗŒcç/ƇƑ$Ƈ

A dyadic Link that accepts either the count of objects (implying [1..N]) or a list of indices on the left and the tuple length on the right and uses the preceding Link as the dyadic comparison function, "f", (in the Try it online links, below, that is in the header section).

Try it online!
Or see an example where r is greater than the number of indices here.
Or see an example where all pairs need comparing here, using f=y-x<=1.

How?

ṗŒcç/ƇƑ$Ƈ - Link: Indices (or Count); TupleLength
ṗ         - {Indices (or [1..Count])} Cartesian power {TupleLength}
        Ƈ - keep those for which:
       $  -   last two links as a monad - g(Tuple):
 Œc       -     unordered pairs
      Ƒ   -     is invariant under?:
     Ƈ    -       keep those for which:
   ç/     -         reduce using the comparison Link (our "f")

(Only for the sake of completeness. I suppose the does not actually satisfy the title "Implement ⧅")

Uiua 0.15.0-dev.2, 5 bytes ^SBCS

⧅^0:⇡

Try on Uiua Pad!

A macro that takes f and returns a function that takes n r. Note that the name of a macro (second-order function) must end with !.

JavaScript (Node.js), 96 bytes

f=>n=>g=r=>r?g(r-1).flatMap(x=>(h=i=>i--?x.every(t=>f(t,i))?[...h(i),[...x,i]]:h(i):[])(n)):[[]]

Try it online!