Chosen's autocomplete is just a bonus. You can have your normal hierarchy using chosen and it is much more accessible than other options you have. I would at least give it a go.
Now considering SHS and CSHS.. they are quite similar and I would not recommend using them side by side.
The main reason for that is that they tackle the same issue with a different approach and -best case scenario- one's functionallity would overwrite the other's.
Now as far as I know they do indeed have compatibility issues as stated in CSHS's module page (at the time this was posted)
It is possible to use the CSHS widget as an exposed filter for taxonomy term reference fields. Please note that this feature might break if SHS module is enabled on your site.
While I think I find CSHS's approach more usable, I would stick with SHS and chosen in your case since you mentioned that your vocabularies are large and CSHS, being client side and all, is more susceptible to performance issues, since it
[...], but in contrast to those modules the whole taxonomy tree is already present at page-load and the whole processing is done "client-side".
Now, to give the devil it's due, both modules have performance issues with very large trees and it is only natural and understandable, but SHS seems like a more stable choice.
Lastly, to achieve what you described, I would prefer a more "Drupal 8" way and would create a new Field Formatter plugin for the entity reference field you are using and attach this to the form in the form display tab of you entity.
To summarize, I would but not use SHS in conjunction with CSHS, and although you have to try it our yourself, the combination of SHS and Chosen seems to me like the obvious choise for your case. Try overriding the entity reference field's field formatter to add
the taxonomy parent name to your options if you prefer a more custom approach.