Subway tile is classic and inexpensive. And since it's white, it will work with the floor and the countertops, whether you keep them or change them in the future. As for a wall color, nothing says "fresh and sunny" like a muted apple green.

Agreed on the subway tile but maybe do the opposite. Use a color for the back splash tile and do the walls white? They have beautiful blues and grays that would look awesome.

I like the suggestion of a light green. We chose an "almond green" for a north-facing kitchen, and even then, it gave a fantastic freshness and fun to the room. A sunny yellow always does the trick too. As for color, you could choose a colorful tile for a backslash, and maybe the same, but much more muted color for the wall. But the white options would be lovely too !

Wow, unless I misunderstood, that's a whole lot of cabinets and storage you are losing if it's those facing us in that picture #2.
I agree that a white tile is timeless and easy to re-decorate around.
Regarding backsplash, I've seen ceiling tins used as backsplash. Also any type of 'scrapbooking' paper that has a pretty design and cover it with plastic or acrylic.
In California, there is a company called TAP PLASTICS and they can cut to size to cover the pretty paper. If that is not an option, I covered all the exposed walls in contact paper. I have a small condo kitchen so it looks cute...not overwhelming. Plus, the design is simple in green and white. Works just fine.

Back painted glass. You can choose any color you want for the back splash. I found an article here on Apartment Therapy that was about using tempered glass shelves as painted back splashes and people either used special glass paint or craft paint made for glass. At Ikea I found a glass shelf that was the the exact length of my stove and I painted it a nice turquoise. I am pairing it with a bright and cheerful grey. I decided that instead of tile (because i just don't have the budget) I would paint magnetic paint as the primer and then the gray over it. That way at least I can use magnets on it. The glass adds the nice spot of color in the right spot too and provides easy clean up for a messy cooking job. Good luck!

Swap the locations of the stove and refrigerator. It'll open up the space!

Benjamin Moore "Pale Avocado" is really pretty and would look great with the Autumn. It's a very buttery green that changes with the light; I used it for a bedroom with western exposure once and loved it. No specific tile suggestions, but recommend keeping them simple.

And yes for swapping the fridge and stove!

LOVE 'Pale Avacado'!! True, you can't go wrong with that color...it does change in different lights, but always heart uplifting! Gorgeous with greys, gorgeous..and still perfectly beautiful and mmmm in shady areas!

I would paint your kitchen a medium brown. I wouldn't get rid of the cabinets though, lots of storage.. I would get a new more modern sink and faucet, it will completely change the look of your kitchen.The floor doesn't look bad and would go with a medium brown walls. Don't paint the kitchen blue. Do the least and save for more important things.

I say stainless tiles for the back splash.

I used small pieces of broken dishware from the thrift store for my back splash. I love it! We're moving now, so I'm trying to decide if I am going to do it again in the new kitchen!

You don't NEED a backsplash. If budget is an issue, just paint the backsplash area the same as the rest of the room. It looks like there is a tiled area around the stove anyhow, so unless you are removing that any backsplash will need to match or coordinate with that. Pale Avocado is a good suggestion. Will you be able to keep the same floor once those cabinets are removed? It might not go all the way to the wall. What about a counter-height long, narrow table under the window, and keep those cabinets. Consider backless stools to reduce visual clutter.

Also like the idea of switching the fridge and stove if possible.

If your budget is super tights, I agree that white subway tiles are a great way to go. If you want to go for something a little more unique, there are some great pictures circulating the web with white subway tiles and a black-ish grout.

If you have a little more money to spend I would go with a white marble 3"x6" tile (super reasonable at home depot! - http://www.homedepot.com/h_d1/N-5yc1v/R-100664302/h_d2/ProductDisplay?catalogId=10053&langId=-1&keyword=marble&storeId=10051)

Either way I love the idea of a soft gray/blue for the walls. Also, if you could swap out your hardware it would make a huge difference. Ikea has some great options to check out. Good luck with your project.

HD has some large vinyl adhesive tiles that look like tin & can be cut to fit your space. I love the idea of back painted glass. I have a small wall mirror mounted behind my stove (with industrial Velcro strips) and it works well as a backsplash, though I kind of think that you don't necessarily need a backsplash back there if you don't cook things that spatter much. I do think some backsplash material is useful around the kitchen sink area. A piece of oilcloth, tailored to fit your space exactly with grommets for hanging could even be hung as a backsplash if you want something inexpensive, bright & easily changeable.

Note regarding swapping the fridge and stove: I agree this would open up space, but you will not be able to open the left side of the fridge fully if you put it up against the wall on the left.

Thank you everybody for your suggestions. I really loved the idea of switching the locations of the stove and fridge, but I'm afraid it's impossible, at least for now. I'd have to remove all upper cabinets and the floor (since the fridge ice maker is connected to the sink through a cable that goes under the floor). Since my budget is so limited, I've decided to leave them alone for now. I did remove the cabinets in pic 2, because I don't need too much storage and I really to have wanted a breakfast area. I've added a cabinet between the stove and the fridge, where I had an empty space. I still haven't decided on the paint, but I'm leaning towards a blue or turquoise. I found one that I like, Limpid Lagoon from SICO, I'm leaning towards using that one on a wall and leaving the rest of the walls white. Also, I loved the idea of painting a backsplash and I think I'll go with it.
thank you everybody for your input. I'll post "after" pictures as soon as I'm done