VBO's can definitely increase your game's performance. To minimize texture changes, you should merge your small textures together and make a few big ones that contain different rectangles for animation-frames and particles (Tilesets). These are especially effective when you want to render particles and terrain tiles. I suggest you make one big texture for all your particles and render them all at once after you rendered the rest of you scene. This would avoid redundant texture changes and make your game alot faster.

Use a quad with appropriate texture coordinates to "select" a tile from your tileset and render it.