You don't HAVE to kill the frogs <img src="/ubbthreads/images/graemlins/winkwink.gif" alt="" />
Even in Act I, the last two areas are very quest-heavy (assuming as Kiya said that you listen to your death knight and use the disguise). And even in the earlier levels of Act I there are quite a few puzzles relating to hidden areas, though you'll have to look for them... they won't jump out at you.
