Search -> Bing: Sadly, you can’t replace the default search engine assigned to your Android phone, even with rooting (unless I’ve missed something). But you can choose to replace the Google search app icon with Bing, replace the voice search default with Bing, and take the extra half-step to tap the “Search with Bing” option whenever you tap the search button or click the search widget.
Calendar -> Exchange setup (or something web-based): This is actually the stumper. Most of the calendar apps in the Android Market are just re-styled interfaces for Google’s own Calendar service. So you can either hook up to your work Exchange server, or perhaps find a good web-based calendar service you can bookmark on your home screen.
YouTube -> Web-based YouTube: I like Vimeo, but many videos are only on YouTube. So, using your alternate browser, and without signing in, simply head to YouTube’s mobile web version and view your videos there. The web version, actually, is often better, and certainly better looking.
In the end, you’ll probably decide that you like the convenience of Google’s offerings on your Android phone. That is, after all, their mission and purpose. But you don’t have to give Google every bit of data about your mobile life, so spreading it around a few different apps can lend some piece of mind about your digital life, if that’s a concern for you. Android is, if not entirely, dictionary-strict “open,” at least rather permissive.