> Shouldn't a new business therefore start with companies that are still smaller and faster at approving expenses?

Yes, that's a valid approach. But only you know what the right market for your product is, however (aka "Product-Market Fit".) Not everything can be sold to every company. Plus you will also realize that your product changes depending on the size of the company.

> How do I get a conversation going? Do you start by giving a general idea about your service?

That's a very broad topic. You may want to start following B2B sales and B2B Marketing blogs to get some best practices for these things. There is absolutely an art and science to these things and it can be learned.