Well I'm just starting out myself so I don't have much room to talk or have much experience, but I have been playing Sierra games since the mid 80's, and have lurked around the AGI community for a few years.
256 color can be done in both AGI & SCI. AGI requires a special patch, I haven't tried it out yet tho, so I'm not sure how effective it is. SCI has much better graphics though. I took a short look at SCI Studio and was a little overwhelmed. Quite a lot to learn. I didn't fool around with it to long tho, but making games in SCI is quite new, and with the exception of the Naturette 2 game being done in SCI, I'm not aware of any others being worked on currently. To work in SCI, I would wait till theres some good tutorials out, I've found a link to one so far. So unless your already an experienced programmer, I'd stick with AGI first. Thats what I plan to do, then after I'm well versed in that, I plan to give SCI a better look.