The reason Android can be relied upon to play nice, is that, as the only one of the platforms with open code access, you can write the app you need to get it to sync correctly with Evolution - or worst case, convert your Evolution files to what the Android's syncing functionality uses. Either of these solutions, which are not currently possible on a majority of other mass-market smartphones, should work to fit your needs - possibly with the hiring of a handy coder or two or paying someone to write it for the Evolution project.
The other nice part about Android is that there's a fair array of sets - great way for the boss to show off his boss-ness by getting a recent top-of-the-line while your group handles (surprisingly cheap for a smartphone!) sets from last year, WITHOUT losing compatibility with the key app you need.
I believe that Blackberries can also support custom apps, though if your business does FOSS for the sake of Freedom, as opposed to simply cost, the Android OS, being GNU GPL (even if the specific implementation in many phones isn't), may better suit your wishes anyhow.