There are a variety of areas to consider regarding the relative restrictiveness of the two platforms.
The Market
Android Market is undoubtedly less restrictive than the App Store when it comes to the submission process. The upside is that you can get pretty much anything you want into the Android Market. The downside is that you can get pretty much anything you want into the Android Market (a market flooded with spam “applications” is in some ways a restriction).
A big negative on the iPhone side is the fact that your options for installing applications that are not in the App Store are limited — you can either distribute the application as a beta (limited to 100 users) or jailbreak your iPhone. Android, however, allows you to install apps from anywhere, including a web page.
The Applications
One of the core design philosophies of the Android platform is “All Applications are Created Equal”, which is supposed to mean that you can freely replace applications on the phone with a third party version. In practice this is not really the case, as many of the Google applications either have special capabilities not available to most applications (see: Android Market) or use undocumented/native APIs (see: Calendar).
The iPhone on the other hand makes no such claims about equality, and the Apple stance in general is “There is only one way to do it, and that is the Apple way”. Additionally third party iPhone applications may not run in the background while Android applications can. New for iPhone OS 4.0 is the ability for apps to run in the background. One thing iPhone applications can currently do that Android applications can not is receive push notifications. New for Android 2.2 is the ability for apps to receive push notifications via something called the Android Cloud.
The Source
Android is open source – mostly (some firmware components are closed source). Even so, there is some rocket science involved just in getting the Android codebase to compile. In addition Google has sent cease & desist orders for redistributing custom images that include the Android Market and Google Maps application.
The iPhone is completely closed source, and recent changes to the developer agreement have been controversial as they mandate that all apps submitted to the app store be originally written in “Objective-C, C, C++, or JavaScript as executed by the iPhone OS WebKit engine, and only code written in C, C++, and Objective-C may compile and directly link against the Documented APIs”
The SDK
The Android SDK can be freely downloaded; the iPhone SDK requires free user registration to download. Android development can be done under Mac OS X, Windows or Linux, while iPhone development is only possible under Mac OS X. You’ll also need to pay for the $99 iPhone developer account if you want to test your software on an actual device (rather than the simulator).
The Userbase
And last but certainly not least, the userbase. When this answer was originally written the iPhone had a much larger userbase and was growing much faster than Android. This is changing as Android begins to support multiple carriers and hardware platforms (see: the Open Handset Alliance). The list of devices running Android is now quite long although none yet match the popularity of the iPhone.
Some analysts are now reporting that Android is outselling the iPhone and are predicting that Android will soon overtake iPhone for market share. Other analysts think that Apple will make up ground when the iPhone 4g is released. The former seems more likely based on the parallel history of the PC industry — Apple’s design and user experience were copied by GoogleMicrosoft and opened up to run on commodity hardware.