To give your character life you have to give him character, you do this usually by giving him a face. Especially the eyes are important. Eyes are the soul of a character. You have the most lifeless eyes you can have in pixel art, so you have to make them different. If you find it too hard to give him different eyes, you can always make him special in other ways, make him look special. give him a long nose, a weird outfit etc.
Now for your walk cycle, you basically just had to frames and changed them a little bit. In motion, you dont'see these small changes, it looks like you just have a 2 frame animation.
http://www.manningkrull.com/pixel-art/walking.php look at this tutorial for a 4 frame walk cycle.
Here are some changes I would make. There is a clear difference between the front and back leg. To create a bigger illusion of movement, his head and arms also move with his steps. His body sways with his legs.