A hello world Flex app can result in a SWF file (the application) which is about 300k. It is likely that downloading that SWF is what is taking time. If so then there are some ways to reduce that file size. The Flex Framework RSLs can reduce the size of a SWF significantly by putting all of the Flex classes into a cross-site, cross-application cache. Also, make sure that you are doing a release build on the project. That also significantly reduces SWF size by removing debugging information.
Flex apps are very different from HTML apps. They run client side and then once loaded they usually only make requests to the server when they need to get or update data. So the initial download size will be more than HTML but then subsequent user interactions should be very responsive. Also binary serialization protocols like AMF can help to significantly reduce the size of data moving over the wire.
Flex apps can run in the browser with Flash Player or on the desktop with Adobe AIR. But it's the same architecture and components used to create either type of application. Also with Adobe AIR the application needs to be installed (along with the Adobe AIR runtime). So Adobe AIR probably won't help you application load any faster.