I am no expert, but have redone the different aspects of the toilets in the house.
Toilets have a certain “equilibrium”. That is if you notice, you cannot fill a normally working toilet to the rim of the bowl. Adding water to the bowl will always cause it to act like it is flushing.
It could be possible that the toilet is leaking from the tank into the bowl slowly and that over time it builds up and “flushes”, but then I would expect it to slowly rise again. You also generally can hear the water leaking from the tank to the bowl.
The flapper valve leaking (IME) generally is heard as running water and seldom empties the bowl (as it is maintaining a slow state of equilibrium).
The fact that two different toilets are doing this at the same outlet would seem to indicate (as others have suggested) that there is an external problem.
Does the toilet flush normally and refill normally?
When the plumber replaced the arm mechanism, was just the arm replaced? the entire flushing mechanism? was the tank removed?
When the new toilet was installed was everything replaced? Including the wax ring under the toilet?
One thing I did not know is some plumbing companies (I am sure this depends on the requirements of plumbers in the area) do not always send out fully trained plumbers. My BIL started working at a plumbing company and had very little training and if he started a job and had to go back, he did not get paid extra and if another plumber had to be sent to fix his mistake, the other plumber got paid and he did not. My point is, if they sent out a rookie because it was just replacing the flushing mechanism, he quite possibly knows nothing about “difficult” plumbing situations and could just be guessing at the solution and figures that saying replace the toilet is the easy fix. Then when that did not work, he does not have anything else to offer but do it again.
Could a bad seal on the wax ring cause the bowl to drain (ie letting air escape due to a faulty ring)?
In looking online, one place had 4 reasons, 1 was a leak (not likely since the first toilet was working fine and the second one was new), 2 fill valve not working properly, but you said it filled fine, just did not stay there, so this is likely not the issue. 3 something caught in the trap and causing a wicking effect, but since the toilet was replaced, again this seems unlikely. leaving the 4th reason a clogged sewer vent pipe.
I assume this is not occurring at any other toilets and there are no strange sounds in the pipes.
So from this I would have to go with the blocked sewer pipe.