Is frequent rebasing something I should push for? A clean history is nice, but I've just won them over on feature branches... Is this something quick and easy that would improve our quality of life?

Realistically, in the short term, no. If neither you nor any of your team members are familiar with rebasing or rebase-based workflows, you will encounter problems that no one will know how to solve without researching. That'll lead to frustration, and before you know it those old school teammates that don't get git will fall back into using svn, or zip files with names like final_project_v1.2_final_final (copy)

I recommend getting familiar with rebase- and merge-based workflows on your own first, like on your own projects/private repos, and reading through the git documentation. Once you become more of an expert, you might be able to teach your teammates how to be proficient at using git, or at bare minimum, you'll be able to help them unfuck themselves when they inevitably fuck their repos up.