Both horizontal (e.g. in a header) and vertical (e.g. in a sidebar) menus should be supported by the Navigation block.
As an example, I'm working on designing a theme right now that would benefit from having a vertical menu block:

Currently, there's no way to achieve this using the navigation block without using a bunch of CSS hacks. Native support would be helpful for achieving this kind of menu design in Gutenberg themes.
Agree this should be achievable. It'd be good to explore using this API for it: #16283.
Notice this could be a great case for using the variations system if we want to make it easily discoverable in the inserter.
The question is then how to add a way to make the navigation vertical.
Some options as I see it.
A control in the sidebar to switch the navigation between horizontal/vertical.
A Styles pattern. User selects the vertical pattern.
A narrow alignment option that pushes the navigation to become vertical.
Styles
Adding a styles vertical pattern.

Alignment
Adding a narrow alignment pushing the navigation to become vertical.

Notice this could be a great case for using the variations system if we want to make it easily discoverable in the inserter.
@mtias are you suggesting have 2 types of navigation blocks?
Btw here is something similar. "[Enhancement] Added a vertical style to the Buttons block."
https://github.com/WordPress/gutenberg/pull/20160#issuecomment-601018891
It would probably be nice with a common approach.
Most helpful comment
As an example, I'm working on designing a theme right now that would benefit from having a vertical menu block:
Currently, there's no way to achieve this using the navigation block without using a bunch of CSS hacks. Native support would be helpful for achieving this kind of menu design in Gutenberg themes.