I was going to wait to use iOS 13 until I got my new iPhone, but will it not let me back up my iCloud and sync it on the new iPhone if its not on the same iOS?
What you can't do is restore from a 13.1 backup onto a 13.0 device (ie. you cannot restore from a backup that was made from a more recent OS than what your new phone is running).
I'm not going to restore. I just usually log into my new iPhone with iCloud account and transfer whatever iCloud saves. I like to start fresh with new phones.