Have a request to change the currency of a parent Entity and want to know what the implications are and the best way to go about it.

I think you have mentioned the 2 easiest ones (alternate structure or just put the new above the old). One other option is the Auto Translation Currencies setting, but that's probably more involved (but cleaner). The new above the old would probably be a good way to go, I think.
Oh, but one downside to that is the base Entities wouldn't be visible in the new parent currency, though.
So, alternate structure or Auto Translation Currencies is probably better
Also take into consideration if your client uses O#DirectElim in reports. If you go with the approach in adding a new parent above the current entity hierarchy, you will not see the DirectElim results on the new parent entity. In this case, an alternate hierarchy would be the best approach if DirectElim is used on the reporting side.