Should I tell the representative on the phone (or my company payroll
department, or anyone for that matter) my bank account / routing
numbers, or should I consider that bad security practice? I suppose
the real question is, how sensitive are these?
Don't give them this information if they called you. It is too easy for somebody to spoof the info being shown on your caller id system. You can't even trust the number it displays.
Now if you need to give them this information to enable to link your accounts, then call them. Lookup the information on their website, or on a statement they have sent you.
Your banking information is sensitive. Yes you do give it to everybody that you send a check to. But you don't want to give it to a random person that calls you.
Yes you should tell the payroll department so that they can directly deposit your paycheck. Your brokerage needs to know so that you can move money in or out of the account. A legitimate business will protect this information.
The regular security advice applies. Only enter this information on a webpage with https. Only enter it on a site that you know is valid.