telnet is no longer included by default in macOS installs, as it is a rarely-used and extremely insecure protocol. When you do have a need for it, you can install it by using one of the standard macOS software port repositories, such as Homebrew, or by compiling and installing it yourself from source. gnu netutils contains one such implementation.

If you're able to simply run telnet from inside Terminal, then that means that you've already installed it somewhere and it's able to be located via your PATH environment variable. You can use which telnet to see where it lives. You can then use that explicit path for your Terminal profile settings.

UPDATE:

Here are steps to configure Terminal to run telnet at startup.

  1. Open Terminal.
  2. Navigate to Terminal > Preferences.
  3. Choose the Profiles tab.
  4. In your default profile, click the Shell tab.
  5. In the field that says "Run command:" replace the existing command with the absolute path to telnet. In your case, that would be /opt/homebrew/bin/telnet.
  6. You may optionally enable or disable the "Run inside shell" option according to your tastes.

Got it working.

Only solution that finally fixed it was to disable SIP, disable authenticated root, mount the root partition, copying telnet to /usr/bin and then committing the changes to the partition.

Telnet works like a charm now.