It's not the size of the Moons so much as the proximity to the sun that makes a 2 moon system (and especially a 2 moon horse-shoe orbit) unstable. Size matters too, but the proximity to the sun matters more. The sun's tidal force perturbs the Moon's orbit around the earth quite a bit. If Earth was much further from the sun, it could have several moons, not just one and some a fair bit more distant and the big moon's orbit would be nearly circular due the inverse tidal forces, which tend to circularize an orbit.
Making the moon's smaller helps some, but what you really need, if you want that orbit to be relatively long-lasting, is to push the Earth away from the sun at least a few more astronomical units.
If we ignore the solar-tidal effects, then Earth could have 2 moons in a horse-shoe orbit to each other. As to what it would look like, the first thing to consider is that everything in the sky rises in the east and sets in the west and that's because the Earth rotates. If you watch each of the two horseshoe moons individually, they would move much like our moon, rising in the east, moving slowly against the fixed stars, and setting in the west.
The second thing to consider is that the Moons, the planets and the sun move against the fixed background stars, but this movement is slow unless the Moon is very close to Earth. Our Moon, moves a full 360 degrees across the fixed stars once every 27 days (sidereal orbit).
The motion of the two moons individually would be very similar to our moon now in terms of new, waxing, full, waning, and repeat.
What the horseshoe orbit would do is you'd see one moon slowly catching up to the other, perhaps touching it from the point of view of earth, but never passing it. it would get close, then it would reverse direction relative to the other moon and in a couple/few weeks, it would approach from the other direction, slow down and reverse. Each moon individual would behave much like our moon but relative to each other there would be this weird game of attraction-repulsion between them.
I believe (but don't quote me on this), from Earth you'd never see the Moons' cross, but you'd perhaps see them touch. The nature of the horeshoe orbit prevents crossing and passing, you'd just see them move closer, then move further away from each other. If you had a really good eye, you might be able to notice the smaller moon change size as it moves closer and further from the Earth as the moon's get close, but that difference would be subtle.
This is the best diagram I've seen for what happens as the moons get close. Unfortunately it's not in English, but it's not hard to follow:
The horseshoe back and forth, assuming some degree of stability, it should have a regular period, just as the full-moons would have a period. The optimal time for moon watching would be when those 2 periods coincide and you have a double full moon. The horseshoe period and the full moon period (currently 29 days - sidereal orbit) should have nothing to do with each other but they could in theory be coincidentally in some kind of resonance.
As pointed out in the other thread, even if the Earth was far enough away from the sun to have two moons in this pattern, it's probably not truly long-term stable. It might last for a few hundred orbits, or a few thousand. It's not what is generally considered a stable orbit.
Would both have the same cycle?
This is a bit of a trick question. On average, yes. The orbital periods would need to be the same for the horseshoe to work when averaged out, but individual orbits would need to vary by a little bit, so the individual orbits wouldn't have the same cycle.
Corrections are welcome if I got any of that not quite right.