I would only speak about importance of sitemap. it surely help any crawler to discover new pages and when any bot discovered new pages within any website it crawl and indexed it for further process (algorithmic). Crawling and indexing is the first thing for ranking (for all search engines).
Another thing is... not all search engines have powerful bot as Google. It takes number of days/months for them to crawl and index particular website. So I would have agreed with OP but it's a Google optimization forum hence all the answers would be based on Google.
Offtopic: I really like OP's approach of to be not relayed on Google. Because ultimate goal of any website is the business it achieved through minimal efforts (I'd happy if I get less business with very less efforts).
I have observed that few small search engines are doing really well these days. Like duckduckgo for example. it's relevancy is quite good and number of search queries has increased over the last year. - https://duckduckgo.com/traffic.html
Lead, follow or leave the way...