I would start with internal tools, something you want to build fast, but you don't need to deploy or make it public-facing. This will give them time to learn how to collaborate by making AGENTS.md, skills, and MCPs (if required).

You get buy in, start having conversations see what AI people have explored. Have they tried claude? Do they prefer other tools? If so why? What are the objections. Actually listen. I’d also showcase what you can do. I love to present what codex has found when debugging something, or a prototype I’ve put together.

If you have the budget pay for subscriptions so they can play around.

Also, you say that development velocity is a big problem, but I would dive into why that is. You may be disappointed when velocity remains the same with AI tools.