Effectivement, il faut que tu "bloques" tes 2 threads en leur faisant appeler wait() sur un même objet, puis ton thread principal pourra ensuite faire un notifyAll() sur cet objet, ce qui les réveillera tous les deux.
Ne t'inquiète pas sur le coup du synchronized : quand un thread se met en "wait", il libère le verrou associé (ce que Sun appelle le "moniteur" de l'objet), ce qui permet à un autre thread de l'obtenir lorsqu'il entre dans un bloc synchronized.
Par contre, à moins de disposer d'une machine réellement multi-processeur, les 2 threads ne se réveilleront pas tout à fait en même temps. L'un se réveillera avant l'autre (la seule garantie que tu as est de ne pas pouvoir prévoir lequel sera réveillé en premier). Par ailleurs, il est vrai que le premier à se réveiller refera automatiquement l'acquisition du moniteur de l'objet sur lequel le synchonized a été fait... donc jusqu'à ce qu'il le libère, tous les autres threads réveillés par le notifyAll() seront remis en attente. En même temps, si la première chose que tu fais après le wait(), c'est sortir du bloc synchronized, tu ne verras pas vraiment que le moniteur as été réacquis : le thread réveillé libèrera le moniteur avant même qu'un autre thread ait eu le temps d'avoir la main.
A la place des basiques wait() et notify(), tu peux aussi utiliser des services plus évolués comme la classe java.util.concurrent.CyclicBarrier. Mais si tu analyses leur source, tu verras que cela revient au même que d'utiliser wait() et notify() (à la complexité de ton code près, ces classes évoluées le simplifiant largement et le rendant largement plus sûr).