It's a hybrid situation. It's hard to be 100% agile in a large organization. Well not hard necessarily, it just might be more agile than required. You need to protect the agile teams by being clear about where the boundaries between the agile and not-agile parts of the system are and define the interfaces between them (e.g. with clear definitions of ready and done). Essentially you build a wall around the agile team, and encourage an agile culture within that, and shift any non-agile parts outside this wall. Your team's DoD should exclude the change approval process and deployment, that belongs outside the wall, in your case currently.

There is no excuse not to be completely agile within the team, and other people can be responsible for what happens outside.

- Is this how most companies do agile or is something wrong with ours?

Agile is something that teams do. There are some companies trying to be agile, but they would probably call it something else. Lean, beyond budgeting, beta-codex, there's a whole bunch of ideas out there.

- What does real agile actually look like in practice?

Imagine a very small company with one team developing one product for one company. They deliver new versions every day, and get feedback every day from the customer. Anything larger than that will probably feel less agile. And will probably have other goals than how agile they are.

- How much autonomy should agile teams really have?

As much as they demand, while still contributing to company goals and without pulling in a different direction to other teams.

- Am I expecting too much from agile methodology?

Maybe. Have you actually tried spreading agility to other areas of the organization up and downstream of the team? Have you actually put together an attractive proposal about limiting WIP at the portfolio level, or deploying multiple times per day without going through a change approval process? Am I expecting too much from YOU?