UltraHLE was fast because it used high level emulation for almost everything (CPU, graphics, sound), it was missing support for several μCodes, it was missing emulation for many framebuffer effects, it had hacks and generally it was designed to achieve higher speed while leaving compatibility and accuracy behind.
Project64 tries to achieve compatibility and accuracy (it uses low level emulation for everything apart from the graphics) and this affects speed. However, it can run less demanding games like Mario 64 on older CPUs (ie: a Pentium 3 at ~500MHz) without noticable slowdowns.
Emulation of newer systems (PS2. GC) is slow because they are faster and demand more resourses than older systems (N64, PSX). If we combine that with their complex architecture and the missing documendation for their internal parts (which leads to time consuming reverse engineering) it is common for their emulators to evolve slowly.
Emulators were never created to replace the actual system. The "success" of Bleem! and UltraHLE made some people believe that. Unfortunately this lead emulation to this state (and by saying "this state" I mean people who ask why they can't run Naruto, Pokemon, Final Fantasy, Zelda, etc.).