I would recommend Number Theory by George E. Andrews. It's great for a general introduction. While there aren't *that* many examples, there are hints and solutions to selected exercises. Additionally, at around $20CDN, if you find the book doesn't suite your needs, at least you didn't break the bank.
Elementary Number Theory and Its Applications by Kenneth H. Rosen is a very broad introduction to number theory. The book covers many topics and has a lot of examples. Perhaps even more importantly, it's written in a clear and sophisticated manner, and is well suited for both beginners and enthusiasts.
Hope this helps!