Could this work, given the nature of our cubicle setup?
Yes it should. Each setup has its own considerations, so the fact that this is a cubicle setup doesn't mean there is no room for ergonomics.
Could asking for this draw unwanted attention or backfire?
No, it shouldn't as long as you do it politely and professionally.
Are they legally obligated to provide this?
As you are in Canada, it seems they are. I am not a lawyer, but this page from the Canadian Centre for Occupational Health and Safety gives several specifications and guidelines on selecting and using Ergonomic chairs. Furthermore, it seems they also have guidelines on Working in a Sitting Poistion, that may be also useful for you to consider.
Further, how could I find out in a future job search how well the company takes care of ergonomics, especially if I am interviewing remotely?
Most likely any company you interview with will take care of ergonomics.
However, if you still want to ask, expose to them your need for an ergonomic/comfortable chair to sit during the job-searching process (email, interviews, etc), and ask if such thing is possible (having a medical note to back you up would be best in any case). This will help you know in advance if ergonomics will be an issue.