How to respond to conflicting environment names in published packages which I inadvertently inflicted on an unsuspecting public?

In the options section, add

\def\prooftree@name{prooftree}
\DeclareOption{altprooftree}{\def\prooftree@name{altprooftree}}

Then in the final part do

\NewEnviron{\prooftree@name}[1]{%
  [...]
}

Thus a user wanting to use bussproofs can load

\usepackage[altprooftree]{prooftrees}

and use altprooftree in the document.

I'd not try to be too fancy with detecting package order etc as it makes the behaviour hard to document.

I'd just have two package options prooftree and tableau and if either option is used then call the environment that.

if neither option is used then it's up to you what the default would be. You could default to tableau so avoiding a clash but make existing users add [prooftrees] if they do not want to change documents or make it default to [prooftrees] unless that environment is already defined in which case it defaults to [tableau] that would make the common case of just loading one package work as before, and the case of loading bussproofs then prooftrees avoid a clash.

that leaves loading bussproofs after prooftrees open to error but you could only avoid that by delaying everything to begin document so probably I wouldn't, just document that the user might need the tableau option or change the package order.