If you have nothing, you cannot write a test because there is nothing to test. This seems pretty obvious to me but never seems to be addressed by proponents of TDD.
In order to write a test, you have to first decide what the method or function looks like that you're going to test. You have to know what parameters to pass to it and what you expect to get back. That is what comes first, not the test.
Tests can never come first. The thing that comes first is the design which specifies what classes and methods are going to exist.
It's true that in order to write a test, the test writer must form some conception on how the test code can interact with the System Under Test. In that sense, conceptual design 'comes first'.
Test-driven development (TDD), however, is valuable because it's not (only) a quality assurance methodology. It's first and foremost a fast feedback loop.
While you may have an initial design in mind, once you start to write a test, you may discover that this design doesn't work (or is awkward to use). This often happens, and should cause you to immediately adjust course.
The red-green-refactor cycle suggests a model to think of TDD. Each such cycle may be a minute or two.
Thus, you may start with an initial design in mind, but then adjust it (or completely rethink it) every other minute.
never seems to be addressed by proponents of TDD
I disagree. Plenty of introductions to TDD discuss this. Two good books that discuss this (and much more) are Kent Beck's Test-Driven Development by Example and Nat Pryce and Steve Freeman's Growing Object-Oriented Code Guided by Tests.