(1) Combat in 4E is slow, yes. Expect an average fight of 5 players against 5 monsters to take between one and two hours. It does help, of course, if the players know what their powers do and have their sheet handy.
(2) You'll really have to answer that for yourself.
(3) That depends. If your players aren't interested in the world, there's some good advice for that in the DMG. On the other hand, if your players think the rules are too complex, they should try a more simple and rules-light RPG (there's numerous RPGs on the web with less than a dozen pages total in the rulebook and with faster combat).
(4) In 4E? Yes, the game assumes and requires it, but only when you're doing combat. If the PCs are sitting in a bar, you don't need a map.