R, 100 81 73 bytes

Edit1: -19 bytes by abandoning the nice all-in-one check-for-primality-and-shared-divisors, and instead using clunkier but shorter separate checks

Edit2: -8 bytes thanks to Giuseppe

f=function(b,n=b)`if`(sum(a<-!n%%2:n)>1&!sum(a&!(b^3-b)%%2:n),n,f(b,n+1))

Try it online!

Sadly, although checking for primality by counting divisors and checking for co-primality by counting shared divisors could be elegantly combined, the ugly code below is actually (quite a bit) shorter...

Thanks to Giuseppe for ruthlessly pruning all the unneccessary variables, parentheses, square-brackets and so on...

How? (code before golfing by Giuseppe)

f=function(b,               # f is recursive function taking argument b (=base)
  n=b,                      # n is number to test for pseudo-primeness; start at b
  a=!n%%2:n,                # a is zero-values of n MOD 2..n = divisors (excluding 1)
  c=!(b^3-b)%%2:n           # c is zero-values of (b-1).b.(b+1) MOD 2..n = divisors of b-1, b or b+1
)
`if`(                       # Now, check whether:
(sum(a)>1)                  #   a is not prime (if it has >1 divisor including itself)
  &!sum(c[a]),              #   and it has no shared divisors with b-1, b or b+1
  n,                        # If both are Ok, then n is a pseudo-prime: return it
  f(b,n+1)                  # otherwise, do recursive call with n+1
)                                   

R, 100 81 73 72 bytes

Edit1: -19 bytes by abandoning the nice all-in-one check-for-primality-and-shared-divisors, and instead using clunkier but shorter separate checks

Edit2: -8 bytes, and then -1 more byte thanks to Giuseppe

f=function(b,n=b)`if`(sum(a<-!n%%2:n)>1&all(!a|(b^3-b)%%2:n),n,f(b,n+1))

Try it online!

Sadly, although checking for primality by counting divisors and checking for co-primality by counting shared divisors could be elegantly combined, the ugly code below is actually (quite a bit) shorter...

Thanks to Giuseppe for ruthlessly pruning all the unneccessary variables, parentheses, square-brackets and so on...

How? (code before golfing by Giuseppe)

f=function(b,               # f is recursive function taking argument b (=base)
  n=b,                      # n is number to test for pseudo-primeness; start at b
  a=!n%%2:n,                # a is zero-values of n MOD 2..n = divisors (excluding 1)
  c=!(b^3-b)%%2:n           # c is zero-values of (b-1).b.(b+1) MOD 2..n = divisors of b-1, b or b+1
)
`if`(                       # Now, check whether:
(sum(a)>1)                  #   a is not prime (if it has >1 divisor including itself)
  &!sum(c[a]),              #   and it has no shared divisors with b-1, b or b+1
  n,                        # If both are Ok, then n is a pseudo-prime: return it
  f(b,n+1)                  # otherwise, do recursive call with n+1
)                                   

R, 100 81 bytes

Edit: -19 bytes by abandoning the nice all-in-one check-for-primality-and-shared-divisors, and instead using clunkier but shorter separate checks

f=function(b,n=b,a=!n%%2:n,c=!(b^3-b)%%2:n)`if`((sum(a)>1)&!sum(c[a]),n,f(b,n+1))

Try it online!

Sadly, although checking for primality by counting divisors and checking for co-primality by counting shared divisors could be elegantly combined, the ugly code below is actually (quite a bit) shorter...

How?

f=function(b,               # f is recursive function taking argument b (=base)
  n=b,                      # n is number to test for pseudo-primeness; start at b
  a=!n%%2:n,                # a is zero-values of n MOD 2..n = divisors (excluding 1)
  c=!(b^3-b)%%2:n           # c is zero-values of (b-1).b.(b+1) MOD 2..n = divisors of b-1, b or b+1
)
`if`(                       # Now, check whether:
(sum(a)>1)                  #   a is not prime (if it has >1 divisor including itself)
  &!sum(c[a]),              #   and it has no shared divisors with b-1, b or b+1
  n,                        # If both are Ok, then n is a pseudo-prime: return it
  f(b,n+1)                  # otherwise, do recursive call with n+1
)                                   

R, 100 81 73 bytes

Edit1: -19 bytes by abandoning the nice all-in-one check-for-primality-and-shared-divisors, and instead using clunkier but shorter separate checks

Edit2: -8 bytes thanks to Giuseppe

f=function(b,n=b)`if`(sum(a<-!n%%2:n)>1&!sum(a&!(b^3-b)%%2:n),n,f(b,n+1))

Try it online!

Sadly, although checking for primality by counting divisors and checking for co-primality by counting shared divisors could be elegantly combined, the ugly code below is actually (quite a bit) shorter...

Thanks to Giuseppe for ruthlessly pruning all the unneccessary variables, parentheses, square-brackets and so on...

How? (code before golfing by Giuseppe)

f=function(b,               # f is recursive function taking argument b (=base)
  n=b,                      # n is number to test for pseudo-primeness; start at b
  a=!n%%2:n,                # a is zero-values of n MOD 2..n = divisors (excluding 1)
  c=!(b^3-b)%%2:n           # c is zero-values of (b-1).b.(b+1) MOD 2..n = divisors of b-1, b or b+1
)
`if`(                       # Now, check whether:
(sum(a)>1)                  #   a is not prime (if it has >1 divisor including itself)
  &!sum(c[a]),              #   and it has no shared divisors with b-1, b or b+1
  n,                        # If both are Ok, then n is a pseudo-prime: return it
  f(b,n+1)                  # otherwise, do recursive call with n+1
)                                   

R, 100 bytes

f=function(b,n=b,a=!sapply(c(n,b+1:-1),`%%`,1:n))`if`((sum(c<-a[,1])>2)&(sum(a[c,-1])<4),n,f(b,n+1))

Try it online!

How?

f=function(b,                       # f is recursive function taking argument b (=base)
  n=b,                              # n is number to test for pseudo-primeness; start at b
  a=!sapply(           ,`%%`,1:n)   # construct matrix a, by applying MOD 1..n to:
            c(n,b+1:-1)             # n, b+1, b, and b-1
 )                                   # and keeping logical NOT of the results
                                    # So: rows of a indicate divisors of n and b+1..b-1
`if`(                               # Now, check whether:
  (sum(c<-a[,1])>2)                 # sum of column 1 is not 2 (if it's 2 then n is prime,
                                    #   because it's only divisors are 1 and itself)
  &(sum(a[c,-1])<4),                # and sum of other columns where column 1 is nonzero
                                    #   are 3 (corresponding to the common divisor 1, 
                                    #   but no other common divisors)
  n,                                # If both are Ok, then n is a pseudo-prime: return it
  f(b,n+1)                          # otherwise, do recursive call with n+1
)

R, 100 81 bytes

Edit: -19 bytes by abandoning the nice all-in-one check-for-primality-and-shared-divisors, and instead using clunkier but shorter separate checks

f=function(b,n=b,a=!n%%2:n,c=!(b^3-b)%%2:n)`if`((sum(a)>1)&!sum(c[a]),n,f(b,n+1))

Try it online!

Sadly, although checking for primality by counting divisors and checking for co-primality by counting shared divisors could be elegantly combined, the ugly code below is actually (quite a bit) shorter...

How?

f=function(b,               # f is recursive function taking argument b (=base)
  n=b,                      # n is number to test for pseudo-primeness; start at b
  a=!n%%2:n,                # a is zero-values of n MOD 2..n = divisors (excluding 1)
  c=!(b^3-b)%%2:n           # c is zero-values of (b-1).b.(b+1) MOD 2..n = divisors of b-1, b or b+1
)
`if`(                       # Now, check whether:
(sum(a)>1)                  #   a is not prime (if it has >1 divisor including itself)
  &!sum(c[a]),              #   and it has no shared divisors with b-1, b or b+1
  n,                        # If both are Ok, then n is a pseudo-prime: return it
  f(b,n+1)                  # otherwise, do recursive call with n+1
)