Ces deux-là ne sont peut-être pas aussi amoureux qu’il ne semble.
Le « ne » est explétif, non nécessaire mais possible.
Le conditionnel pour le verbe « sembler » est possible : il apporte une notion de doute plus élevé, par forcément utile ici, puisqu’on a déjà l’adverbe « peut-être ».

Ils ont des problèmes plus graves que de chercher la vérité sur l’accident
La préposition « de » ne pose pas de problème en soi : elle peut ou non être utilisée devant un infinitif.
Les deux éléments d’une comparaison doivent être de même nature. ici on a un nom et un infinitif.
> Ils ont des problèmes plus graves que la quête de la vérité concernant l’accident.

Une classe de petits élèves sort avec sa maîtresse.
Le sujet est bien « classe » qui ne peut être considéré comme un quantificateur.

Il faut que la moitié, voire les trois-quarts des salariés, aient voté.
. Si le nom de fraction ou de pourcentage est précédé d’un article ou d’un adjectif au pluriel
Si le nom de fraction ou de pourcentage est précédé d’un article ou d’un adjectif au pluriel, le verbe s’accorde obligatoirement au pluriel.
 Obs
Suivi d’un complément de nom, l’accord se fait généralement avec « moitié », donc au singulier lorsque le calcul est exact (« La moitié des présents a accepté cette motion ») alors que lorsque la division est approximative, on emploie plutôt le pluriel —Cordial
>> c’est donc bien le pluriel qui est requis ici.

Je vous remercie, Tara, pour ces précisions détaillées.