they gain the ability to set the is_superuser flag on any account, including their own. (!!!)
Not only this, they also gain the ability to give themselves any permissions one-by-one, same effect...
  I'm sure it involves subclassing django.contrib.auth.forms.UserChangeForm
Well, not necessarily. The form you see in the change page of django's admin is dynamically created by the admin application, and based on UserChangeForm, but this class barely adds regex validation to the username field.
  and hooking it into my already-custom UserAdmin object... 
A custom UserAdmin is the way to go here. Basically, you want to change the fieldsets property to something like that :
class MyUserAdmin(UserAdmin):
    fieldsets = (
        (None, {'fields': ('username', 'password')}),
        (_('Personal info'), {'fields': ('first_name', 'last_name', 'email')}),
        # Removing the permission part
        # (_('Permissions'), {'fields': ('is_staff', 'is_active', 'is_superuser', 'user_permissions')}),
        (_('Important dates'), {'fields': ('last_login', 'date_joined')}),
        # Keeping the group parts? Ok, but they shouldn't be able to define
        # their own groups, up to you...
        (_('Groups'), {'fields': ('groups',)}),
    )
But the problem here is that this restriction will apply to all users. If this is not what you want, you could for example override change_view to behave differently depending on the permission of the users. Code snippet :
class MyUserAdmin(UserAdmin):
    staff_fieldsets = (
        (None, {'fields': ('username', 'password')}),
        (_('Personal info'), {'fields': ('first_name', 'last_name', 'email')}),
        # No permissions
        (_('Important dates'), {'fields': ('last_login', 'date_joined')}),
        (_('Groups'), {'fields': ('groups',)}),
    )
    def change_view(self, request, *args, **kwargs):
        # for non-superuser
        if not request.user.is_superuser:
            try:
                self.fieldsets = self.staff_fieldsets
                response = UserAdmin.change_view(self, request, *args, **kwargs)
            finally:
                # Reset fieldsets to its original value
                self.fieldsets = UserAdmin.fieldsets
            return response
        else:
            return UserAdmin.change_view(self, request, *args, **kwargs)