Looking for remote-only positions is hard as most companies don't want to hire outside their own country, meaning that 95% of companies that post on remote job boards are out of the question. Of course I understand that the clerical necessities would be too much for a small startup to want to deal with.
Your point about introducing my desire for remote work after I've proven how awesome I am is probably the best way to go about this, seeing how I'm shooting myself in the foot by talking about it in the first interview. My experience with it at former workplaces hasn't been completely positive (the suggestion always seems to cause an apprehensive reaction), but I realize that I need to make it worth it for them and prove that I'm worth it.
As embarrassing as it is to ask such an entitled question, I'm quite happy for the feedback.